Compute fast log base 2 ceiling

If you can limit yourself to gcc, there are a set of builtin functions which return the number of leading zero bits and can be used to do what you want with a little work:

int __builtin_clz (unsigned int x)int __builtin_clzl (unsigned long)int __builtin_clzll (unsigned long long)

This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.

int ceil_log2(unsigned long long x){  static const unsigned long long t[6] = {    0xFFFFFFFF00000000ull,    0x00000000FFFF0000ull,    0x000000000000FF00ull,    0x00000000000000F0ull,    0x000000000000000Cull,    0x0000000000000002ull  };  int y = (((x & (x - 1)) == 0) ? 0 : 1);  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;}#include <stdio.h>#include <stdlib.h>int main(int argc, char *argv[]){  printf("%d\n", ceil_log2(atol(argv[1])));  return 0;}

If you're compiling for 64-bit processors on Windows, I think this should work. _BitScanReverse64 is an intrinsic function.

#include <intrin.h>__int64 log2ceil( __int64 x ){  unsigned long index;  if ( !_BitScanReverse64( &index, x ) )     return -1LL; //dummy return value for x==0  // add 1 if x is NOT a power of 2 (to do the ceil)  return index + (x&(x-1)?1:0);}

For 32-bit, you can emulate _BitScanReverse64, with 1 or 2 calls to _BitScanReverse.Check the upper 32-bits of x, ((long*)&x)[1], then the lower 32-bits if needed, ((long*)&x)[0].