c - Compute fast log base 2 ceiling

Question

What is a fast way to compute the (long int) ceiling(log_2(i)), where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found here, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.

For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3

Edit: So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks or register methods, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is (n&(n-1)).

Edit 2: A good source on integer logarithms and leading zeroes methods is Sections 5-3 and 11-4 in Hacker's Delight by Henry S. Warren. This is the most complete treatment I've found.

Edit 3: This technique looks promising: https://stackoverflow.com/a/51351885/365478

Answer 1

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)