The opposite of 2 ^ n

Question

The function a = 2 ^ b is quickly calculated for any b, doing a = 1 << b . How about a different path, getting the value b for any given a? It should be relatively fast, so magazines are out of the question . Everything that is not O (1) is also bad.

I would be pleased with what cannot be done if it is simply impossible to get around without magazines or a type of search.

Answer 1

Create a lookup table. For 32-bit integers, there are a total of 32 entries, so O (1).

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

For 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 kind of thing, I usually link to this page using bit hacks:

• Bit Tweedling Hacks

For example:

Find the integer database 2 using the 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 several O (log (n)) algorithms defined on this page.

Answer 3

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

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

This is O (1).

Answer 4

Or you can write:

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

This is O (1). You can imagine that this can be expanded to:

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

When optimizing the classification, when once (a >> x) > 0) returns false, the remainder will not be calculated. Also comparing with 0 is faster than any other comparison. Also: where k is a maximum of 32 and g is 1.

Link: Big O Badge

But if you use BigInteger, then my sample code will look like this:

  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 5

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

If you can crack the binary representation, you can get the exponent. Check the IEEE standard to find out where and how the exhibitor is stored.

For an integer value, if any method of obtaining the most significant bit position is not available, you can binary search for bits for the highest 1, which is therefore O (log numbits). Doing this can actually be faster than converting to double first.

Answer 6

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

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

Answer 7

This cannot be done without testing the high bit, but most modern FPUs support log2, so all is not lost.