coptimizationmath64-bitbit-manipulation

Compute fast log base 2 ceiling


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

Edit 4: C23 is apparently adding stdc_first_(leading/trailing)_(one/zero)


Solution

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