Fast computing of log2 for 64-bit integers

by

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.

More Related Contents:

  1. What’s bad about shifting a 32-bit variable 32 bits?
  2. Compute fast log base 2 ceiling
  3. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  4. Are the shift operators () arithmetic or logical in C?
  5. How can I multiply and divide using only bit shifting and adding?
  6. What is CHAR_BIT?
  7. Extracting bits with a single multiplication
  8. Bitfield manipulation in C
  9. Fastest way to clamp a real (fixed/floating point) value?
  10. Using intptr_t instead of void*?
  11. C left shift on 64 bits fail
  12. warning: left shift count >= width of type
  13. set the m-bit to n-bit [closed]
  14. Bitshift and integer promotion?
  15. Bit twiddling: which bit is set?
  16. How to define and work with an array of bits in C?
  17. Implementing Logical Right Shift in C
  18. How do I get bit-by-bit data from an integer value in C?
  19. Algorithm to generate bit mask
  20. What’s sizeof(size_t) on 32-bit vs the various 64-bit data models?
  21. How does this bitwise operation check for a power of 2?
  22. Check if a number is non zero using bitwise operators in C
  23. How to replace bits in a bitfield without affecting other bits using C
  24. Decimal to Binary
  25. What decides the sizeof an integer?
  26. C Programming – XOR Bitwise Operation
  27. Size of pid_t, uid_t, gid_t on Linux
  28. Bitwise shifting array of char’s
  29. How to implement Bitcount using only Bitwise operators?
  30. What is bit masking?

Leave a Comment