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

Question

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 !!!!

Be clear on your condition "x will always be an integer". If that `x` is an `int` or is `x` a FP with a whole number value? — chux - Reinstate Monica, May 28 '15 at 02:27
By the way, I think you should probably be using `CHAR_BIT` rather than `8` if you value portability, though the use of the intrinsic function probably makes that less important :-) — paxdiablo, May 28 '15 at 07:07

paxdiablo · Answer 1 · 2015-05-28T05:11:05.703

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

You are right about what " 2^(ceil(log2(x))) " represents. You are solution is also correct (obviously). I am not sure whether it will be faster than the one I have though (I might run both later to find out). Anyways, still a pretty neat and intuitive solution (gave it a thumbs up). Thanks — Haider, May 28 '15 at 05:22
@Haider, it may not be faster than the solution you already have for platforms that _have_ a `__builtin_clzll()` intrinsic but it'll probably work better on those that don't :-) — paxdiablo, May 28 '15 at 05:36

score 2 · Accepted Answer · answered May 28 '15 at 02:20

2

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.

answered May 28 '15 at 02:20

Nemo

70,042
10
116
153

Thanks for the quick answer. I could have come up with that on my own (face palm). As an aside, is there anything else wrong with my solution? Any foreseeable portability problems ? – Haider May 28 '15 at 02:26
2

`__builtin_clzll` is a GCC extension. It is almost certainly supported by Clang and the Intel C compiler, but I do not know about Microsoft. Also your final result can be bigger than `int`. And it probably overflows in any event when the input gets bigger than 2^63... Basically I would suggest considering the boundary cases carefully (x=0, x very large). – Nemo May 28 '15 at 02:30
1

Sure this "compute log(x-1) rounded down and add 1" works for exact powers of 2 like 1,2,4? – chux - Reinstate Monica May 28 '15 at 02:49
1

@chux: For 2,4,8,..., yes, I am sure it works. For x=1, I suppose it fails because `__builtin_clzll` is undefined for 0 (see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html). So you need to special-case x=1 for this solution. It should still be significantly faster than a loop, at least on x86 where clz (aka. bsr) is a single instruction. – Nemo May 28 '15 at 14:50

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

2 Answers2