What's the quickest way to compute log2 of an integer in C#?

Question

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

int bits = 1 + log2(100);

=> bits == 7

Solution 1

The Cleanest and Quickest... (works in .Net core 3.1 and up and takes the performance lead starting in .Net 5.0)

int val = BitOperations.Log2(x);

Runner up... (fastest in versions below .Net 5, 2nd place in .Net 5)

int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;

Notes:

• The idea of using the exponent in a floating-point was inspired by SPWorley 3/22/2009.
• This also supports more than 32 bits. I have not tested the max but did go to at least 2^38.
• Use with caution on production code since this can possibly fail on architectures that are not little-endianness.

Here are some benchmarks: (code here: https://github.com/SunsetQuest/Fast-Integer-Log2)

                                      1-2^32                  32-Bit  Zero 
Function                Time1 Time2 Time3 Time4 Time5 Errors Support Support 
Log2_SunsetQuest3       18     18    79167  19    18    255      N       N
Log2_SunsetQuest4       18     18    86976  19    18      0      Y       N
LeadingZeroCountSunsetq -      -        -   30    20      0      Y       Y
Log2_SPWorley           18     18    90976  32    18   4096      N       Y
MostSigBit_spender      20     19    86083  89    87      0      Y       Y
Log2_HarrySvensson      26     29    93592  34    31      0      Y       Y
Log2_WiegleyJ           27     23    95347  38    32      0      Y       N
Leading0Count_phuclv     -      -        -  33    20    10M      N       N
Log2_SunsetQuest1       31     28    78385  39    30      0      Y       Y
HighestBitUnrolled_Kaz  33     33   284112  35    38   2.5M      N       Y
Log2_Flynn1179          58     52    96381  48    53      0      Y       Y
BitOperationsLog2Sunsetq -      -        -  49    15      0      Y       Y
GetMsb_user3177100      58     53   100932  60    59      0      Y       Y
Log2_Papayaved         125     60   119161  90    82      0      Y       Y
FloorLog2_SN17         102     43   121708  97    92      0      Y       Y
Log2_DanielSig          28     24   960357  102  105     2M      N       Y
FloorLog2_Matthew_Watso 29     25    94222  104  102      0      Y       Y
Log2_SunsetQuest2      118    140   163483  184  159      0      Y       Y
Msb_version            136    118  1631797  212  207      0      Y       Y
Log2_SunsetQuest0      206    202   128695  212  205      0      Y       Y
BitScanReverse2        228    240  1132340  215  199     2M      N       Y
Log2floor_version       89    101 2 x 10^7  263  186      0      Y       Y
UsingStrings_version  2346   1494 2 x 10^7 2079 2122      0      Y       Y
                                                                           
Zero_Support = Supports Zero if the result is 0 or less
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf on small numbers)
Time3 = time to run entire 1-2^32 in sequence using Parallel.For. Most results range will on the larger end like 30/31 log2 results. (note: because random was not used some compiler optimization might have been applied so this result might not be accurate) 
Time4 = .Net Core 3.1
Time5 = .Net 5

Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 3.1

I really like the one created by spender in another post. This one does not have the potential architecture issue and it also supports Zero while maintaining almost the same performance as the float method from SPWorley.

Update 3/13/2020: Steve noticed that there were some errors in Log2_SunsetQuest3 that were missed.

Update 4/26/2020: Added new .Net Core 3's BitOperations.LeadingZeroCount() as pointed out by phuclv.

Solution 2

Slight improvement to Guffa's answer... Since the amount you are adding to the result is always a power of two using bit operations can produce slight improvement on some architectures. Also since our context is bit patterns it is slightly more readable to use hexadecimal. In this case it is useful to shift the arithmetic by a 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;
}

Further a check for n==0 should be added since the above will yield a result of 0 and Log(0) is undefined (regardless of base).

In ARM assembly this algorithm produces very compact code as the branch after comparison can be eliminated with conditional instructions which avoids pipeline flushing. For Example:

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

becomes (let R0 = n, R1 = bits)

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

Solution 3

You can simply count how many times you have to remove bits until the value is zero:

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

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

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

Edit:

The most efficient method would be to use the binary steps that Flynn1179 suggested (upvoted for the inspiration :), but expanding 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++;
}

Solution 4

Efficiency in terms of lines of code, or runtime execution speed?

Code's easy: Math.log(n, 2).

Runtime speed's a little trickier, 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% certain I've got the logic right there, but hopefully the idea's clear. There might be some overheads in the .NET VM, but in principle it should be faster.

The 16 in the for loop initialializer is based on half the number of bits needed for an int. If you're working with longs, start it at 32, etc.

Solution 5

In .NET Core 3.0 there are BitOperations.LeadingZeroCount() and BitOperations.Log2. They're mapped to the underlying hardware instructino like x86's LZCNT/BSR so that should be the most efficient solution

int bits = BitOperations.Log2(x); // or
int bits = x == 0 ? 1 : 32 - BitOperations.LeadingZeroCount(x);

View more solutions

Comments

[Filip Navara]

graphics.stanford.edu/~seander/bithacks.html ... choose your poison :)

[Emond]

How about negative numbers? They would appear to be pretty cheap :)

[Flynn1179]

Negatives always need max; the top bit's set.

[Guffa]

@Emo: Good point. This only works for positive numbers. To handle negative numbers just add a if (n < 0) { bits = 32; } else { ... } around the loop.

[Guffa]

That logic doesn't work, as the number that you can represent with a specific number of bits can't be added. 2^24 isn't 2^16 + 2^8 but 2^16 * 2^8.

[Flynn1179]

Well, that's not entirely true, it's not adding 2^16+2^8, it's adding 16+8, which SHOULD work, but there's an error somewhere else I can't quite put my finger on how to fix at the moment; I'll edit when I do. The principle of a 'binary search' should work though, if you can get the logic at each step right.

[Flynn1179]

Fixed it; I had got the logic slightly wrong, and you need to start with 1 bit, not 0.

[Guffa]

the code is not directly adding 2^16+2^8, but subtracting each from the number, in the n-=s; statement. The bitmask should be formed from b-1 rather than b, and instead of subtracting s from the number, you would need to discard the least b bits of the number: int s = 1 << (b - 1); if (n >= s) { n >>=b; bits+=b; }.

[Guffa]

If you start from 1, then the number 0 still needs one bit.

[Guffa]

Although this method has fewer iterations, that doesn't make up for the added logic. I checked the performance, and this method is faster than the first method that I suggested (but only for large numbers), and slower than the second method that I suggested. Anyhow, the execution time ranges from 30 to 80 nanoseconds, so you rarely need anything faster than the simplest possible method. :)

[Flynn1179]

Fair enough; I think for very large numbers it would probably be faster in pure ASM/C, but yeah, if the performance is still lightning fast with simpler code, go with the more maintainable option, definitely.

[harold]

ASM? might as well use BSR then. C? _BitScanReverse or equivalent.

[Zéychin]

Sure they do; log(-5) = log(5)+i pi, for example.

[Zéychin]

That's why complex data types were created, such as in Fortran, and easily implementable in the C-derived languages.

[Guffa]

@Zéychin: You can use an imaginary data type to describe how many imaginary bits you need to store the number, but you can't use it to actually store the number. So, calculating the imaginary bits is totally useless.

[Flynn1179]

Heh, how long have I gone without noticing that overload! Updated the answer, thanks.

[Suraj Jain]

It wont work when we use 32 in initializer, due to this.

[Kind Contributor]

This seems to be slightly faster out of 10M iterations than (int)ceiling(log(value)/log(2)). (int)ceiling(Log(value,2)) is actually slightly slower than both methods, but Log(value,2) is much easier to remember and reuse across projects, the slight slow-down isn't a concern.

[izb]

Is the line "a.asInt = 0;" redundant? What does that part do?

[SunsetQuest]

Without the "a.asInt = 0;", the compiler throws an error of an uninitiated value for some reason when it runs across the "a.asInt >> 23". Maybe the compiler does not take into account the "a.asFloat = val;" that also initialized it. Sorry for replying 7 years late; hopefully, this will help someone else that falls upon this fastest-integer-log2 question.

[phuclv]

BitOperations.LeadingZeroCount() should be faster if you have .NET Core 3.0+

[SunsetQuest]

@phuclv - I was for sure thinking the LEadingZeroCount would be faster but it's actually 50% slower than the top one.

[SunsetQuest]

"int bits = x == 0 ? 1 : 64 - BitOperations.LeadingZeroCount(x);" I think you would want "int bits = 31 - BitOperations.LeadingZeroCount(x);" maybe.

[phuclv]

should be int bits = 32 - BitOperations.LeadingZeroCount(x); for 32-bit ints if you want it to return 1 for 1 and 7 for 100

[phuclv]

@Sunsetquest I guess it has something to do with AMD. PDEP & PEXT are very slow on AMD and probably the same to LZCNT/TZCNT?

[SunsetQuest]

Are you sure? Log2(1) is 0. But if you use "int bits = 32 - BitOperations.LeadingZeroCount(x);" and put in a 1 for x it comes out to 1.

[phuclv]

@Sunsetquest yes it's 0, therefore 1 + log2(1) as the OP expected will result in 1

[phuclv]

wow I didn't even noticed there's BitOperations.Log2. But can you tell me how to build your project? I'm trying it on my PC but it always compiles to BenchmarkLeading0Count.dll instead of an exe file

[SunsetQuest]

@phuclv It should just open with the VS 2017/2019 IDE. I just tested it. VS will compile the console app to a dll but it also places an exe next to it that it runs. It will be interesting what you get on an intel chip.