Count leading zeroes in an Int32
https://stackoverflow.com/questions/10439242
-
05-06-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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.
Solution
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
}
OTHER TIPS
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;
}
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;
}
In .NET Core 3.0 there are BitOperations.LeadingZeroCount() and BitOperations.TrailingZeroCount() which map to the x86's LZCNT/BSR and TZCNT/BSF directly. As a result currently they'll be the most efficient solution
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);
}
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.
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).
private int GetIntegerOffsetLength(int value)
{
return (32 - (Convert.ToString(value, 2).Length);
}
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.
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);
}
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)
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.
32 - Convert.ToString(2,2).Count()
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);
}
}
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));
}
