# Nearest power of two

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 = {      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.

## One thought on “Nearest power of two”

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