CODEWITHSUNDEEP
cmathcastingbit-manipulation
Haider
Haider

Reputation: 341

C : Fast Exponentiation (Power 2) + Binary Logarithm (Rounded up) for Integers

I am trying to find the fastest way to compute the following in C:

p = 2^(ceil(log2(x)));

So far, looking at answers in Stack overflow (and other places) I have got this far:

#define LOG2(X) ((int) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
int p = 1 << LOG2( (unsigned long long)x );

x will always be an integer (type int) and greater than zero. I got the LOG2 solution from this stackoverflow question. There are several good answer but all of them seem to be rounding down (including this one). I need to round up. I am not comfortable enough with the solutions to modify them to round up. Any help would be appreciated !!!!

Upvotes: 1

Views: 476

Answers (2)

paxdiablo
paxdiablo

Reputation: 881623

I'm pretty certain that:

2^(ceil(log2(x)))

can be read as the lowest power of two that's greater than or equal to x, other than where x is zero, where it's undefined.

In which case, it can be found with something like:

unsigned int fn (unsigned int x) {
    if (x == 0) return 0;
    unsigned int result = 1;
    while ((result < x) && (result != 0))
        result <<= 1;
    return result;
}

which is relatively efficient, needing at most one iteration per number of bits in the data type (32 for a 32-bit integer, for example).

This will return either the correct power of two, or zero on error (if the input number is zero, or the result is not able to be represented in the data type).

You can see it in action in the following program:

#include <stdio.h>
#include <limits.h>

unsigned int fn (unsigned int x) {
    if (x == 0) return 0;
    unsigned int result = 1;
    while ((result < x) && (result != 0))
        result <<= 1;
    return result;
}

int main (void) {
    printf ("%u -> %u\n\n", 0, fn(0));
    for (unsigned int i = 1; i < 20; i++)
        printf ("%u -> %u\n", i, fn(i));
    printf ("\n%u -> %u\n", UINT_MAX, fn(UINT_MAX));
    return 0;
}

which outputs:

0 -> 0

1 -> 1
2 -> 2
3 -> 4
4 -> 4
5 -> 8
6 -> 8
7 -> 8
8 -> 8
9 -> 16
10 -> 16
11 -> 16
12 -> 16
13 -> 16
14 -> 16
15 -> 16
16 -> 16
17 -> 32
18 -> 32
19 -> 32

4294967295 -> 0

Upvotes: 4

Nemo
Nemo

Reputation: 71535

What the heck, I'll make this an answer.

To convert "round down" to "round up", just compute log(x-1) rounded down and add 1 to the result.

In general, the result of rounding something up is always 1 more than rounding down (i.e. floor(something) and ceil(something) differ by 1), except when the something is an exact integer; in this case, when your input is a power of 2. The trick of subtracting 1 from the input and adding 1 to the result is general; it will work for any monotonic function like log().

For complete correctness you might want to special case 0 as input, but that is true for your original formulation, too, since log(0) is undefined.

Upvotes: 2

Related Questions