Fast computing of log2 for 64-bit integers

Question

A great programming resource, Bit Twiddling Hacks, proposes (here) the following method to compute log2 of a 32-bit integer:

#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n static const char LogTable256[256] =  {     -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,     LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),     LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) };  unsigned int v; // 32-bit word to find the log of unsigned r;     // r will be lg(v) register unsigned int t, tt; // temporaries if (tt = v >> 16) {     r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else  {     r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; } 

and mentions that

The lookup table method takes only about 7 operations to find the log of a 32-bit value. If extended for 64-bit quantities, it would take roughly 9 operations.

but, alas, doesn't give any additional info about which way one should actually go to extend the algorithm to 64-bit integers.

Any hints about how a 64-bit algorithm of this kind would look like?

Answer 1

Intrinsic functions are really fast, but still are insufficient for a truly cross-platform, compiler-independent implementation of log2. So in case anyone is interested, here is the fastest, branch-free, CPU-abstract DeBruijn-like algorithm I've come to while researching the topic on my own.

const int tab64[64] = {     63,  0, 58,  1, 59, 47, 53,  2,     60, 39, 48, 27, 54, 33, 42,  3,     61, 51, 37, 40, 49, 18, 28, 20,     55, 30, 34, 11, 43, 14, 22,  4,     62, 57, 46, 52, 38, 26, 32, 41,     50, 36, 17, 19, 29, 10, 13, 21,     56, 45, 25, 31, 35, 16,  9, 12,     44, 24, 15,  8, 23,  7,  6,  5};  int log2_64 (uint64_t value) {     value |= value >> 1;     value |= value >> 2;     value |= value >> 4;     value |= value >> 8;     value |= value >> 16;     value |= value >> 32;     return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58]; } 

The part of rounding down to the next lower power of 2 was taken from Power-of-2 Boundaries and the part of getting the number of trailing zeros was taken from BitScan (the (bb & -bb) code there is to single out the rightmost bit that is set to 1, which is not needed after we've rounded the value down to the next power of 2).

And the 32-bit implementation, by the way, is

const int tab32[32] = {      0,  9,  1, 10, 13, 21,  2, 29,     11, 14, 16, 18, 22, 25,  3, 30,      8, 12, 20, 28, 15, 17, 24,  7,     19, 27, 23,  6, 26,  5,  4, 31};  int log2_32 (uint32_t value) {     value |= value >> 1;     value |= value >> 2;     value |= value >> 4;     value |= value >> 8;     value |= value >> 16;     return tab32[(uint32_t)(value*0x07C4ACDD) >> 27]; } 

As with any other computational method, log2 requires the input value to be greater than zero.

Answer 2

If you are using GCC, a lookup table is unnecessary in this case.

GCC provides a builtin function to determine the amount of leading zeros:

Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

So you can define:

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1)) 

and it will work for any unsigned long long int. The result is rounded down.

For x86 and AMD64 GCC will compile it to a bsr instruction, so the solution is very fast (much faster than lookup tables).

Working example:

#include <stdio.h>  #define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))  int main(void) {     unsigned long long input;     while (scanf("%llu", &input) == 1) {         printf("log(%llu) = %u\n", input, LOG2(input));     }     return 0; } 

Compiled output: https://godbolt.org/z/16GnjszMs