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

Answer 1

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

Answer 2

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++;
}

Answer 3

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.

Answer 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.

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

Answer 6

direct convert to IEEE754 32bit has wrong result after about 33554431

public unsafe static int ByPtr754_32(ulong bits) {
    var fp = (float)bits;
    return (int)(((*(uint*)&fp >> 23) & 255) - 127);
}

convert to FP64 and ILogB has wrong result after 53bits, about 18014398509481983

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}
public static int ByILogB(ulong bits) {
    return Math.ILogB(bits);
}

lg and ln has wrong after about 47bits, about 281474976710655

static readonly double ln2 = Math.Log(2.0), divLn2 = 1 / ln2;
public static int ByLn(ulong bits) {
    //return (int)(Math.Log(bits) * divLn2);
    return (int)(Math.Log(bits) / ln2);
}

lb wrong after 48bits, about 562949953421311

public static int ByLog2(ulong bits) {
    return (int)Math.Log2(bits);
}

Binary Search is very slow.

public static int BySearch(ulong bits) {
    if (0 == bits) {
        return -1;
    }

    int min = 0, max = 64;
    for (; ; ) {
        int mid = (max + min) >> 1;
        if (mid == min) {
            break;
        }
        if (bits >> mid != 0) {
            min = mid;
        } else {
            max = mid;
        }
    }
    return min;
}

My suggestion is here: Fast one:

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
static readonly int[] _TableMix = CreateTableMix();
public static int ByTableMix(ulong bits) {
    int r;
    return (r = _TableMix[bits >> Fp64Prec]) > 0 ? r : ByPtr754_64(bits);
}

Simple one:

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
public static int By754Adj(ulong bits) {
    const int lack = 64 - Fp64Prec;
    int r;
    return (r = ByPtr754_64(bits >> lack)) > 0 ? r+lack : ByPtr754_64(bits);
}

Speed test result:

 Search: 649830
 ByTest: 535859
 ByLog2: 560492
   ByLn: 376675
   ByLg: 392090
 ByILog: 252594
Table16: 136847
ByUnion: 123453
 754_64: 101358
 754_32: 118379
TableMx: 106201
 754Adj: 174889