Count leading zeroes in an Int32

Question

How do I count the leading zeroes in an Int32? So what I want to do is write a function which returns 30 if my input is 2, because in binary I have 000...0000000000010.

Deluna

But... that value does not have 30 leading zeros. – Serai

Could you take another stab at explaining what you're trying to accomplish, please? An int doesn't have "leading zeroes", and the string "0000000000000010" does not contain 30 of anything. What are you actually trying to do? "Counting leading zeroes" doesn't sound like the real problem. – Jampacked

Should it return 30 because representing 2 requires 2 bits of a 32-bit integer? – Jampacked

I think he means that a 32 bit integer would have 30 leading zeroes since the binary value would theoretically be 000000000000000000000000000010 – Deyo

The answer can be done by ANDing various powers of 2 to find the highest power of 2 represented, and then that should tell you have many "leading" zeroes there are. – Deyo

This is strangely similar to this question. – Jampacked

@Deyo No this is not homework. I don't know how to do it so I asked a question. I try to answer questions I know the answer to. – Deluna

@Richard1987 - Then you failed to show What have you tried? – Deyo

Answer 1

NOTE Using dotnet core >=3.0? Look here.

Let's take the number 20 as an example. It can be stated in binary as follows:

    00000000000000000000000000010100

First we "smear" the most significant bit over the lower bit positions by right shifting and bitwise-ORing over itself.

    00000000000000000000000000010100
 or 00000000000000000000000000001010 (right-shifted by 1)
 is 00000000000000000000000000011110

then

    00000000000000000000000000011110
 or 00000000000000000000000000000111 (right-shifted by 2)
 is 00000000000000000000000000011111

Here, because it's a small number, we've already completed the job, but by continuing the process with shifts of 4, 8 and 16 bits, we can ensure that for any 32-bit number, we have set all of the bits from 0 to the MSB of the original number to 1.

Now, if we count the number of 1s in our "smeared" result, we can simply subtract it from 32, and we are left with the number of leading zeros in the original value.

How do we count the number of set bits in an integer? This page has a magical algorithm for doing just that ("a variable-precision SWAR algorithm to perform a tree reduction"... if you get it, you're cleverer than me!), which translates to C# as follows:

int PopulationCount(int x)
{
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return (x & 0x0000003f);
}

By inlining this method with our "smearing" method above, we can produce a very fast, loop-free and conditional-free method for counting the leading zeros of an integer.

int LeadingZeros(int x)
{
    const int numIntBits = sizeof(int) * 8; //compile time constant
    //do the smearing
    x |= x >> 1; 
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    //count the ones
    x -= x >> 1 & 0x55555555;
    x = (x >> 2 & 0x33333333) + (x & 0x33333333);
    x = (x >> 4) + x & 0x0f0f0f0f;
    x += x >> 8;
    x += x >> 16;
    return numIntBits - (x & 0x0000003f); //subtract # of 1s from 32
}

Aspia

Hi, thank you very much. I was wondering if there was anything built into C# to do this though. I'll take this as a no, given that I didn't find anything either. – Deluna

The Ones function computes the Hamming weight. There's a description of the algorithm on the wikipedia page of that name. – Delphinedelphinia

Also want to throw out there that I benchmarked this against coercing to a double and then reading the exponent bits. This implementation is still faster. hamming weight: 1550887 ticks, fpu: 1861061 ticks. Thats DateTime ticks for 10000000 iterations, btw. – Delphinedelphinia

@Delphinedelphinia Is it possible to improve the algorithm exploiting the fact that x always 2^n-1? – Peonage

Yep. According to Wikipedia's "Find first set" (the count leading zeros problem is also discussed) page: table[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31} return table[(x × 0x07C4ACDD) >> 27] from the 4th code block in the algorithms section (citing Leiserson, Prokop, and Randall). Whether this implementation is faster (it may very well be) will be determined by someone who isn't slacking off at work. ;) – Delphinedelphinia

I realize this is an old thread and the method is more the focus than the values, but 10 (decimal) is not 00000000000000000000000000010100 in binary, it's 00000000000000000000000000001010. I'd recommend you either change the binary values or just say we're using 20 for this example. – Fivepenny

I benchmarked about 25 different versions in c# and besides a couple that extract a floats exponent, yours was 30% fast then the next. After spending some time looking at all these, this function is actually pretty amazing and is the best because it extracting the exponent could possibly be problematic on non-little-endian architectures or some compiler configurations. Nice work! – Daedal

Answer 2

In .NET Core 3.0 there are BitOperations.LeadingZeroCount() and BitOperations.TrailingZeroCount() which map to the hardware instructions directly if available, for example LZCNT/BSR and TZCNT/BSF on x86, or CLZ/CTZ on ARM. As a result currently they should be the most efficient solution

Piacular

This is the best answer for .NET Core 3.0 and above. It is safe because it is built-in to the default .net core library and the performance is probably tuned with handcrafted asm instructions for each platform. – Daedal

Answer 3

If you'd like to mix assembly code in for peak performance. Here's how you do that in C#.

First the supporting code to make it possible:

using System.Runtime.InteropServices;
using System.Runtime.CompilerServices;
using static System.Runtime.CompilerServices.MethodImplOptions;

/// <summary> Gets the position of the right most non-zero bit in a UInt32.  </summary>
[MethodImpl(AggressiveInlining)] public static int BitScanForward(UInt32 mask) => _BitScanForward32(mask);

/// <summary> Gets the position of the left most non-zero bit in a UInt32.  </summary>
[MethodImpl(AggressiveInlining)] public static int BitScanReverse(UInt32 mask) => _BitScanReverse32(mask);


[DllImport("kernel32.dll", SetLastError = true)]
private static extern IntPtr VirtualAlloc(IntPtr lpAddress, uint dwSize, uint flAllocationType, uint flProtect);

private static TDelegate GenerateX86Function<TDelegate>(byte[] x86AssemblyBytes) {
    const uint PAGE_EXECUTE_READWRITE = 0x40;
    const uint ALLOCATIONTYPE_MEM_COMMIT = 0x1000;
    const uint ALLOCATIONTYPE_RESERVE = 0x2000;
    const uint ALLOCATIONTYPE = ALLOCATIONTYPE_MEM_COMMIT | ALLOCATIONTYPE_RESERVE;
    IntPtr buf = VirtualAlloc(IntPtr.Zero, (uint)x86AssemblyBytes.Length, ALLOCATIONTYPE, PAGE_EXECUTE_READWRITE);
    Marshal.Copy(x86AssemblyBytes, 0, buf, x86AssemblyBytes.Length);
    return (TDelegate)(object)Marshal.GetDelegateForFunctionPointer(buf, typeof(TDelegate));
}

Then here's the assembly to generate the functions:

[UnmanagedFunctionPointer(CallingConvention.Cdecl)]
private delegate Int32 BitScan32Delegate(UInt32 inValue);

private static BitScan32Delegate _BitScanForward32 = (new Func<BitScan32Delegate>(() => { //IIFE   
   BitScan32Delegate del = null;
   if(IntPtr.Size == 4){
      del = GenerateX86Function<BitScan32Delegate>(
         x86AssemblyBytes: new byte[20] {
         //10: int32_t BitScanForward(uint32_t inValue) {
            0x51,                                       //51                   push        ecx  
            //11:    unsigned long i;
            //12:    return _BitScanForward(&i, inValue) ? i : -1;
            0x0F, 0xBC, 0x44, 0x24, 0x08,               //0F BC 44 24 08       bsf         eax,dword ptr [esp+8] 
            0x89, 0x04, 0x24,                           //89 04 24             mov         dword ptr [esp],eax 
            0xB8, 0xFF, 0xFF, 0xFF, 0xFF,               //B8 FF FF FF FF       mov         eax,-1               
            0x0F, 0x45, 0x04, 0x24,                     //0F 45 04 24          cmovne      eax,dword ptr [esp]
            0x59,                                       //59                   pop         ecx 
            //13: }
            0xC3,                                       //C3                   ret  
      });
   } else if(IntPtr.Size == 8){
      del = GenerateX86Function<BitScan32Delegate>( 
         //This code also will work for UInt64 bitscan.
         // But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process.  
            x86AssemblyBytes: new byte[13] {
            //15:    unsigned long i;
            //16:    return _BitScanForward64(&i, inValue) ? i : -1; 
            0x48, 0x0F, 0xBC, 0xD1,            //48 0F BC D1          bsf         rdx,rcx
            0xB8, 0xFF, 0xFF, 0xFF, 0xFF,      //B8 FF FF FF FF       mov         eax,-1 
            0x0F, 0x45, 0xC2,                  //0F 45 C2             cmovne      eax,edx  
            //17: }
            0xC3                              //C3                   ret 
         });
   }
   return del;
}))();


private static BitScan32Delegate _BitScanReverse32 = (new Func<BitScan32Delegate>(() => { //IIFE   
   BitScan32Delegate del = null;
   if(IntPtr.Size == 4){
      del = GenerateX86Function<BitScan32Delegate>(
         x86AssemblyBytes: new byte[20] {
            //18: int BitScanReverse(unsigned int inValue) {
            0x51,                                       //51                   push        ecx  
            //19:    unsigned long i;
            //20:    return _BitScanReverse(&i, inValue) ? i : -1;
            0x0F, 0xBD, 0x44, 0x24, 0x08,               //0F BD 44 24 08       bsr         eax,dword ptr [esp+8] 
            0x89, 0x04, 0x24,                           //89 04 24             mov         dword ptr [esp],eax 
            0xB8, 0xFF, 0xFF, 0xFF, 0xFF,               //B8 FF FF FF FF       mov         eax,-1  
            0x0F, 0x45, 0x04, 0x24,                     //0F 45 04 24          cmovne      eax,dword ptr [esp]  
            0x59,                                       //59                   pop         ecx 
            //21: }
            0xC3,                                       //C3                   ret  
      });
   } else if(IntPtr.Size == 8){
      del = GenerateX86Function<BitScan32Delegate>( 
         //This code also will work for UInt64 bitscan.
         // But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process. 
            x86AssemblyBytes: new byte[13] {
            //23:    unsigned long i;
            //24:    return _BitScanReverse64(&i, inValue) ? i : -1; 
            0x48, 0x0F, 0xBD, 0xD1,            //48 0F BD D1          bsr         rdx,rcx 
            0xB8, 0xFF, 0xFF, 0xFF, 0xFF,      //B8 FF FF FF FF       mov         eax,-1
            0x0F, 0x45, 0xC2,                  //0F 45 C2             cmovne      eax,edx  
            //25: }
            0xC3                              //C3                   ret 
         });
   }
   return del;
}))();

In order to generate the assembly I started a new VC++ project, created the functions I wanted, then went to Debug-->Windows-->Disassembly. For compiler options I disabled inlining, enabled intrinsics, favored fast code, omitted frame pointers, disabled security checks and SDL checks. The code for that is:

#include "stdafx.h"
#include <intrin.h>  

#pragma intrinsic(_BitScanForward)  
#pragma intrinsic(_BitScanReverse) 
#pragma intrinsic(_BitScanForward64)  
#pragma intrinsic(_BitScanReverse64) 


__declspec(noinline) int _cdecl BitScanForward(unsigned int inValue) {
    unsigned long i;
    return _BitScanForward(&i, inValue) ? i : -1; 
}
__declspec(noinline) int _cdecl BitScanForward64(unsigned long long inValue) {
    unsigned long i;
    return _BitScanForward64(&i, inValue) ? i : -1;
}
__declspec(noinline) int _cdecl BitScanReverse(unsigned int inValue) {
    unsigned long i;
    return _BitScanReverse(&i, inValue) ? i : -1; 
}
__declspec(noinline) int _cdecl BitScanReverse64(unsigned long long inValue) {
    unsigned long i;
    return _BitScanReverse64(&i, inValue) ? i : -1;
}

Catharine

What a cool way to inline assembly in C#! I was looking for a way to use BSR for this. Worth noting that this "should" be the fastest way to do this, but it's also architecture-specific (not that many of us are using .NET on anything but x86). This needs more upvotes. – Telegram

Note that when I tested it, it was actually slower on dotnet 4.7.2 because of the ~50 instruction overhead of going from managed to unmanaged code. Assembly functions would have to be much fatter to offset that overhead. – Catharine

That's really interesting. I wonder if it's the same overhead branching out to C++/CLI? That's how I usually bring assembly into the managed space, mostly because I can control the marshalling. Unfortunately, Core isn't going to support C++/CLI, so hopefully the overhead has gotten better. – Telegram

Answer 4

Look at https://chessprogramming.wikispaces.com/BitScan for good info on bitscanning.

If you're able to mix assembly code then use the modern LZCNT, TZCNT and POPCNT processor commands.

Other than that take a look at Java's implementation for Integer.

/**
 * Returns the number of zero bits preceding the highest-order
 * ("leftmost") one-bit in the two's complement binary representation
 * of the specified {@code int} value.  Returns 32 if the
 * specified value has no one-bits in its two's complement representation,
 * in other words if it is equal to zero.
 *
 * <p>Note that this method is closely related to the logarithm base 2.
 * For all positive {@code int} values x:
 * <ul>
 * <li>floor(log<sub>2</sub>(x)) = {@code 31 - numberOfLeadingZeros(x)}
 * <li>ceil(log<sub>2</sub>(x)) = {@code 32 - numberOfLeadingZeros(x - 1)}
 * </ul>
 *
 * @param i the value whose number of leading zeros is to be computed
 * @return the number of zero bits preceding the highest-order
 *     ("leftmost") one-bit in the two's complement binary representation
 *     of the specified {@code int} value, or 32 if the value
 *     is equal to zero.
 * @since 1.5
 */
public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

Armagnac

Answer 5

Try this:

static int LeadingZeros(int value)
{
   // Shift right unsigned to work with both positive and negative values
   var uValue = (uint) value;
   int leadingZeros = 0;
   while(uValue != 0)
   {
      uValue = uValue >> 1;
      leadingZeros++;
   }

   return (32 - leadingZeros);
}

Didache

I've modified the method to use unsigned integer shifting, otherwise with negative values it will never exit the loop. – Bunnybunow

Answer 6

If you just want to simulate Lzcnt instruction you can do it like this (it gives 32 for zero value):

int Lzcnt(uint value)
{
    //Math.Log(0, 2) is -Infinity, cast to int is 0x80000000
    int i=(int)Math.Log(value, 2);
    return 31-(i&int.MaxValue)-(i>>31);
}

If you need to know how many bits are necessary to store particular value, better will be:

1+((int)Math.Log(value, 2)&int.MaxValue)

Above gives one for zero value – as you need one bit to store zero actually.

But those will only work for uint and not for ulong. Double (which is Log method argument) hasn’t got enough precision to store ulong up to the least significant bit, so (double)0xFFFFFFFFFFFFFF is indistinguishable from (double)0x100000000000000.

But with .Net Core 3.0 we finally have the latest and greatest Lzcnt instruction available. So if only System.Runtime.Intrinsics.X86.Lzcnt.IsSupported (System.Runtime.Intrinsics.X86.Lzcnt.X64.IsSupported for ulong) then you can use System.Runtime.Intrinsics.X86.Lzcnt.LeadingZeroCount(value) (System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount(value) for ulong).

But with .Net Core 3.0 we finally have the latest and greatest System.Numerics.BitOperations.LeadingZeroCount as @phuclv already mentioned here.

Benzo

Answer 7

Some complicated answers going on here. How about this?

private int LeadingZeroes(int value)
{
    return (32 - (Convert.ToString(value, 2).Length));
}

Though now I'm guessing there might be some issues with negative numbers and whatnot with this type of solution.

Aguila

The biggest issue with this solution is that it requires memory allocation plus is very very slow due to serialization. – Reedy

Answer 8

In C:

unsigned int
lzc(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(WORDBITS - ones(x));
}

(from http://aggregate.org/MAGIC/#Leading Zero Count)

Translation into C# is left as a trivial exercise to the reader.

EDIT

The reason I gave the link was, that I need not copy the following (again In C):

#define WORDBITS 32

unsigned int
ones(unsigned int x)
{
        /* 32-bit recursive reduction using SWAR...
       but first step is mapping 2-bit values
       into sum of 2 1-bit values in sneaky way
    */
        x -= ((x >> 1) & 0x55555555);
        x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
        x = (((x >> 4) + x) & 0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return(x & 0x0000003f);
}

Subterfuge

I think this just moves the main part of the work to ones(x) – Dorseydorsiferous

what is WORDBITS and what is ones(x)? - the answer is very incomplete currently at best – Blackjack

Answer 9

Come on guys, stop asking "why you want do this or that". Answer if you can or just go on. Counting leading zeros is a common task in many problems (e.g. compression algorithms). There are even x86 hardware instructions dedicated to that (clz, bsr). Unfortunately, you cannot use those hardware instructions in C#, because intrinsics are not supported (yet). Conversion into a string was a joke I suppose.

Binary representation of int has very well defined bounds. In fact, in C# int is just alias for Int32. As its namge suggests, "Int32" is always 32 bit signed integer, even if you compile your project for x64.

And you dont need some special voodo magic to compute leading zeros: Here is simple math solution that works:

Here "x" is your int (Int32):

int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);

Edit: Sorry, I have reviewed and corrected my formula. Because of precision errors of double arithmetic, the result may be incorrect for few boundary cases. So it still needs some "voodo magic". The second line handles those cases and produces correct result.

Idiotic

it's also very slow because of Math.Log – Piacular

Answer 10

I think the best choice is spender's post above. However, if someone is looking for a slight performance boost the following can be used.. (note: it is only 2% faster in benchmarks on my machine)

This one works by converting a float to an int and then grabbing the exponent bits.

    [StructLayout(LayoutKind.Explicit)]
    private struct ConverterStruct
    {
        [FieldOffset(0)] public int asInt;
        [FieldOffset(0)] public float asFloat;
    }

    public static int LeadingZeroCount(uint val)
    {
        ConverterStruct a;  a.asInt = 0; a.asFloat = val;
        return 30-((a.asInt >> 23 )) & 0x1F;
    }

This could also be stretched to an Int64 version also...

    [StructLayout(LayoutKind.Explicit)]
    private struct ConverterStruct2
    {
        [FieldOffset(0)] public ulong asLong;
        [FieldOffset(0)] public double asDouble;
    }

    // Same as Log2_SunsetQuest3 except
    public static int LeadingZeroCount(ulong val)
    {
        ConverterStruct2 a;  a.asLong = 0; a.asDouble = val;
        return 30-(int)((a.asLong >> 52)) & 0xFF;
    }

Notes: The idea of using the exponent in a float is from SPWorley 3/22/2009. Use with caution on production code since this would fail on architectures that are not little-endianness.

Here are some benchmarks for Floor-Log2 - this is almost the same: https://github.com/SunsetQuest/Fast-Integer-Log2)

Daedal

Answer 11

count leading zeros/find first set/bit scan reverse is such a common thing to want in OS and other low level programing most hardware supports clz in to form of a single cycle instruction. And most c/c++ compilers have a compiler intrinsic for it.

http://en.wikipedia.org/wiki/Find_first_set

also most hardware and compilers also have count trailing zeros,pop count/bit count/count ones, parity, bswap/flip endien, and several other quarky but highly useful bit twiddling operations.

Bluestocking

Answer 12

You can got best performance using pre-computed counts

public static class BitCounter
{
    private static readonly int[] _precomputed = new[]
        {
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
        };

    public static int CountOn(int value)
    {
        return _precomputed[value >> 24] +
               _precomputed[(value << 8) >> 24] +
               _precomputed[(value << 16) >> 24] +
               _precomputed[value & 0xFF];
    }

    public static int CountOff(int value)
    {
        return 32 - CountOn(value);
    }
}

Mowry

Your algorithm doesn't count leading zeros, but all zeros. Not what the OP is asking about. – Peonage

Lookup tables are generally faster in benchmarks only. In real-world operation, they can be slower because they require the lookup table to be in the cache. If it's not, it's a cache miss, and you lose cycles. The fastest (and most reliable) algorithms are usually pure mathematical operations without branches or lookup tables. – Telegram

Answer 13

32 - Convert.ToString(2,2).Count()

Annoying

Answer 14

Integers don't have leading zeros, nor do they support 32 digits. That being said, you should be able to create a function to do this by converting the integer to a string, and checking the length:

private int GetIntegerOffsetLength(int value)
{
    //change 32 to whatever your upper bound is
    return (32 - (value.ToString().Length + 1));
}

Kursk

I think he wants it converted to binary first – Aguila

wrong answer- max length of a 32 bit integer in base 10 is not 32 – Blackjack

@BrokenGlass: I know what the max length of an integer is. OP specifically asked for the difference from 32. My comment about adjusting the upper bound was anticipating that. – Kursk