How to find a binary logarithm very fast? (O(1) at

Question

Is there any very fast method to find a binary logarithm of an integer number? For example, given a number x=52656145834278593348959013841835216159447547700274555627155488768 such algorithm must find y=log(x,2) which is 215. x is always a power of 2.

The problem seems to be really simple. All what is required is to find the position of the most significant 1 bit. There is a well-known method FloorLog, but it is not very fast especially for the very long multi-words integers.

What is the fastest method?

Answer 1

You can create an array of logarithms beforehand. This will find logarithmic values up to log(N):

#define N 100000
int naj[N];

naj[2] = 1;
for ( int i = 3; i <= N; i++ )
{
    naj[i] = naj[i-1];
    if ( (1 << (naj[i]+1)) <= i )
        naj[i]++;

}

The array naj is your logarithmic values. Where naj[k] = log(k). Log is based on two.

Answer 2

Is Bit Twiddling Hacks what you're looking for?

Answer 3

A quick hack: Most floating-point number representations automatically normalise values, meaning that they effectively perform the loop Christoffer Hammarström mentioned in hardware. So simply converting from an integer to FP and extracting the exponent should do the trick, provided the numbers are within the FP representation's exponent range! (In your case, your integer input requires multiple machine words, so multiple "shifts" will need to be performed in the conversion.)

Answer 4

If the integers are stored in a uint32_t a[], then my obvious solution would be as follows:

1. Run a linear search over a[] to find the highest-valued non-zero uint32_t value a[i] in a[] (test using uint64_t for that search if your machine has native uint64_t support)

2. Apply the bit twiddling hacks to find the binary log b of the uint32_t value a[i] you found in step 1.

3. Evaluate 32*i+b.

Answer 5

The answer is implementation or language dependent. Any implementation can store the number of significant bits along with the data, as it is often useful. If it must be calculated, then find the most significant word/limb and the most significant bit in that word.

Answer 6

The best option on top of my head would be a O(log(logn)) approach, by using binary search. Here is an example for a 64-bit ( <= 2^63 - 1 ) number (in C++):

int log2(int64_t num) {
    int res = 0, pw = 0;    
    for(int i = 32; i > 0; i --) {
        res += i;
        if(((1LL << res) - 1) & num)
            res -= i;
    }
    return res;
}

This algorithm will basically profide me with the highest number res such as (2^res - 1 & num) == 0. Of course, for any number, you can work it out in a similar matter:

int log2_better(int64_t num) {
    var res = 0;
    for(i = 32; i > 0; i >>= 1) {
        if( (1LL << (res + i)) <= num )
            res += i;
    }
    return res;
}

Note that this method relies on the fact that the "bitshift" operation is more or less O(1). If this is not the case, you would have to precompute either all the powers of 2, or the numbers of form 2^2^i (2^1, 2^2, 2^4, 2^8, etc.) and do some multiplications(which in this case aren't O(1)) anymore.