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

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 2

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 3

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 4

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