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

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; }