What is the fastest way to calculate log2 integer in C #?

Question

How can I most efficiently calculate the number of bits needed by an integer (base base 2) in C #? For example:

int bits = 1 + log2(100); => bits == 7 

Answer 1

Efficiency in terms of lines of code or runtime speed?

Easy code: Math.log(n, 2) .

The execution speed is a bit more complicated, but you can do it with a kind of "binary search":

 int bits = 1; for (int b = 16; b >=1; b/=2) { int s = 1 << b; if (n >= s) { n>>=b; bits+=b; } } 

I'm not 100% sure that I have logic, but I hope the idea is clear. There may be some overhead in the .NET VM, but in principle it should be faster.

16 in the for loop initializer is based on half the number of bits needed for an int. If you work with longs, run it on 32, etc.

Answer 2

A slight improvement in Guffa's answer ... Since the amount you add to the result always has the power of two bit operations, it can lead to a slight improvement in some architectures. Also, since our context is bit patterns, it is a bit more readable to use hexadecimal. In this case, it is useful to shift the arithmetic to the power of 2.

 int bits = 0; if (n > 0xffff) { n >>= 16; bits = 0x10; } if (n > 0xff) { n >>= 8; bits |= 0x8; } if (n > 0xf) { n >>= 4; bits |= 0x4; } if (n > 0x3) { n >>= 2; bits |= 0x2; } if (n > 0x1) { bits |= 0x1; } 

Next, a check should be added for n == 0, since the above will give the result 0, and Log (0) - undefined (regardless of the base).

In the ARM assembly, this algorithm creates a very compact code, since the branch after comparison can be eliminated using conditional instructions that avoid flushing the pipeline. For example:

 if (n > 0xff) { n >>= 8; bits |= 0x8; } 

becomes (let R0 = n, R1 = bit)

 CMP R0, $0xff MOVHI R0, R0, LSR $8 ORRHI R1, R1, $0x8 

Answer 3

You can simply count how many times you need to delete bits until the value becomes zero:

 int bits = 0; while (n > 0) { bits++; n >>= 1; } 

More efficient for large numbers, you can first count the groups of bits:

 int bits = 0; while (n > 255) { bits += 8; n >>= 8; } while (n > 0) { bits++; n >>= 1; } 

Edit:

The most effective method would be to use the binary steps proposed by Flynn1179 (to support inspiration :), but extending the loop into hard-coded checks. This is at least twice as fast as the method above, but also more code:

 int bits = 0; if (n > 32767) { n >>= 16; bits += 16; } if (n > 127) { n >>= 8; bits += 8; } if (n > 7) { n >>= 4; bits += 4; } if (n > 1) { n >>= 2; bits += 2; } if (n > 0) { bits++; }