I was inspired by some code that I saw on StackOverflow that computed base-two logarithms in O(log2(N)) operations, where N is the number of bits in the integer. The following function computes the nearest power of two that is not less than a given value. I've compiled it with gcc and clang, and it optimizes into branch-free code.

` int nearest_power_of_two(int x)`

{

unsigned int z = ((x > 0) ? x - 1 : 0);

z |= z >> 1;

z |= z >> 2;

z |= z >> 4;

z |= z >> 8;

z |= z >> 16;

return (int)(z + 1);

}

Here is a related function, a simple log2() calculator for 64-bit values. Unlike the function above, it rounds down instead of rounding up. Note that the compiler should automatically unroll the loop:

` int log2_int(unsigned long long x)`

{

static const unsigned long long t[6] = {

0xFFFFFFFF00000000ull,

0x00000000FFFF0000ull,

0x000000000000FF00ull,

0x00000000000000F0ull,

0x000000000000000Cull,

0x0000000000000002ull

};

int y = 0;

int j = 32;

int i;

for (i = 0; i < 6; i++) {

int k = (((x & t[i]) == 0) ? 0 : j);

y += k;

x >>= k;

j >>= 1;

}

return y;

}

More efficient implementations exist that use CPU intrinsics, but I love the simplicity of these algorithms. I can't claim credit for either of these, since they are just slight modifications of existing code.

You deserve credit for the second method. This is a non-trivial rewrite which, as you note, also optimizes into branchless code.