Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast computing of log2 for 64-bit integers

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?

like image 458
Desmond Hume Avatar asked Jul 07 '12 15:07

Desmond Hume


People also ask

How is log2 implemented?

How it works: The input integer x is casted to float and then reinterpret as bits. The IEEE float format stores the exponent in bits 30-23 as an integer with bias 127, so by shifting it 23 bits to the right and subtracting the bias, we get log2(x).

How do you create a 64-bit integer?

You can declare 8-, 16-, 32-, or 64-bit integer variables by using the __intN type specifier, where N is 8, 16, 32, or 64. The types __int8 , __int16 , and __int32 are synonyms for the ANSI types that have the same size, and are useful for writing portable code that behaves identically across multiple platforms.

What is 64-bit integer data type?

A 64-bit signed integer. It has a minimum value of -9,223,372,036,854,775,808 and a maximum value of 9,223,372,036,854,775,807 (inclusive). A 64-bit unsigned integer. It has a minimum value of 0 and a maximum value of (2^64)-1 (inclusive).


2 Answers

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.

like image 152
Desmond Hume Avatar answered Oct 08 '22 09:10

Desmond Hume


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

like image 34
kay Avatar answered Oct 08 '22 10:10

kay