The opposite of 2 ^ n

Question

The function a = 2 ^ b can quickly be calculated for any b by doing a = 1 << b. What about the other way round, getting the value of b for any given a? It should be relatively fast, so logs are out of the question. Anything that's not O(1) is also bad.

I'd be happy with can't be done too if its simply not possible to do without logs or a search type thing.

Answer 1

It can't be done without testing the high bit, but most modern FPUs support log2 so all is not lost.

Answer 2

Build a look-up table. For 32-bit integers, there are only 32 entries so it is O(1).

Most architectures also have an instruction to find the position of the most significant bit of a number a, which is the value b. (gcc provides the __builtin_clz function for this.)

For a BigInt, it can be computed in O(log a) by repeatedly dividing by 2.

int b = -1;
while (a != 0) {
  a >>= 1;
  ++ b;
}

Answer 3

For this sort of thing I usually refer to this page with bit hacks:

• Bit Twiddling Hacks

For example:

Find the log base 2 of an integer with a lookup table:

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -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];
}

There are also a couple of O(log(n)) algorithms given on that page.

Answer 4

Some architectures have a "count leading zeros" instruction. For example, on ARM:

MOV R0,#0x80      @ load R0 with (binary) 10000000
CLZ R1,R0         @ R1 = number of leading zeros in R0, i.e. 7

This is O(1).

Answer 5

Or you can write:

while ((a >>= 1) > 0) b++;

This is O(1). One could imagine this to be expanded to:

b = (((a >> 1) > 0) ? 1 : 0) + (((a >> 2) > 0) ? 1 : 0) + ... + (((a >> 31) > 0) ? 1 : 0);

With a complier optimization, that once (a >> x) > 0) returns false, rest won't be calculated. Also comparing with 0 is faster then any other comparison. Also: , where k is maximum of 32 and g is 1.

Reference: Big O notation

But in case you where using BigInteger, then my code example would look like:

    int b = 0;
    String numberS = "306180206916083902309240650087602475282639486413"
            + "866622577088471913520022894784390350900738050555138105"
            + "234536857820245071373614031482942161565170086143298589"
            + "738273508330367307539078392896587187265470464";
    BigInteger a = new BigInteger(numberS);

    while ((a = a.shiftRight(1)).compareTo(BigInteger.ZERO) > 0) b++;

    System.out.println("b is: " + b);

Answer 6

If a is a double rather than an int then it will be represented as mantissa and exponent. The exponent is the part you are looking for, as this is the logarithm of the number.

If you can hack the binary representation then you can get the exponent out. Look up the IEEE standard to see where and how the exponent is stored.

For an integral value, if some method of getting the most significant bit position is not available then you can binary-search the bits for the upper-most 1 which is therefore O(log numbits). Doing this may well actually perform faster than converting to a double first.

Answer 7

In Java you can use Integer.numberOfLeadingZeros to compute the binary logarithm. It returns the number of leading zeros in the binary representation, so

• floor(log2(x)) = 31 - numberOfLeadingZeros(x)
• ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)