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

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?

Solution 1

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.)

Solution 2

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.

Solution 3

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.

Solution 4

If you're using fixed-width integers then the other answers already have you pretty-well covered.

If you're using arbitrarily large integers, like int in Python or BigInteger in Java, then you can take advantage of the fact that their variable-size representation uses an underlying array, so the base-2 logarithm can be computed easily and quickly in O(1) time using the length of the underlying array. The base-2 logarithm of a power of 2 is simply one less than the number of bits required to represent the number.

So when n is an integer power of 2:

• In Python, you can write n.bit_length() - 1 (docs).
• In Java, you can write n.bitLength() - 1 (docs).

Solution 5

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.

View more solutions

Comments

[Ankit Roy]

I don't believe a binary search will work here, since a[] is not sorted -- there will be 0-words both before and after the single word containing a single 1-bit.

[ndim]

Uhm. Of course. What was I thinking? Linear search will be the only thing to work there. I have updated the answer accordingly.

[Todd Lehman]

Note: If the segments of the integer are stored in an array, then the data structure holding the integer (of which the array is a component) should already have the base-2 logarithm kept on hand at all times for instant access. That is, a library that always knows the base-2 logarithm of a giant integer is going to be much more efficient at addition, multiplication, etc., than one which has to scan for it.

[greybeard]

How does this allow to find the binary logarithm of [a multi-words] power of 2 fast?

[Turkhan Badalov]

@greybeard, it is for small numbers to not compute each time logarithm calling log2 from cmath, because it is expensive. This tecnique is often used when creating Sparse tables.