计算Int32中的前导零

如何计算Int32中的前导零？ 所以我想要做的是写一个函数，如果我的输入Int32是2，则返回30，因为在二进制中我有0000000000000010。

Answer 1

我们以数字10为例。 它可以用二进制表示如下：

  00000000000000000000000000010100 

首先，我们通过右移和自身逐位或运算“涂抹”较低位位置上的最高位。

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

然后

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

在这里，因为它是一个很小的数字，我们已经完成了这项工作，但是通过重复这个过程直到16位的右移，我们可以确保对于任何32位数，我们设置了所有位0到原始数字的MSB为1。

现在，如果我们在“模糊”结果中计算1的数量，我们可以简单地从32减去它，并且我们留下原始值中前导零的数量。

我们如何计算整数中的设置位数？ 这个页面有一个神奇的算法来做到这一点（“ 一个可变精度的SWAR算法来执行树减少 ”……如果你得到它，你比我聪明！），它转换为C＃，如下所示：

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

通过使用上面的“涂抹”方法内联这个方法，我们可以生成一个非常快速，无循环且无条件的方法来计算整数的前导零。

 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 } 

Answer 2

试试这个：

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

Answer 3

这里有一些复杂的答案。 这个怎么样？

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

虽然现在我猜测可能存在一些负数的问题以及这种类型的解决方案。

Answer 4

有关比特扫描的详细信息， 请查看https://chessprogramming.wikispaces.com/BitScan 。

如果您能够混合汇编代码，那么使用现代LZCNT，TZCNT和POPCNT处理器命令。

除此之外，请查看Java的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. * * 
Note that this method is closely related to the logarithm base 2. * For all positive {@code int} values x: * 
 * 
floor(log2(x)) = {@code 31 - numberOfLeadingZeros(x)} * 
ceil(log2(x)) = {@code 32 - numberOfLeadingZeros(x - 1)} * 
 * * @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; }
 

Answer 5

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

Answer 6

来吧，伙计们，不要再问“为什么要做这个或那个”。 如果可以或只是继续，请回答。 计数前导零是许多问题（例如压缩算法）中的常见任务。 甚至还有专用于它的x86硬件指令（clz，bsr）。 遗憾的是，您无法在C＃中使用这些硬件指令，因为尚不支持内在函数。 我想，转换成字符串是一个笑话。

int的二进制表示具有非常明确的边界。 实际上，在C＃中int只是Int32的别名。 正如它的namge所暗示的那样，“Int32”总是32位有符号整数，即使您为x64编译项目也是如此。

并且您不需要一些特殊的voodo魔法来计算前导零：以下是简单的数学解决方案：

这里“x”是你的int（Int32）：

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

编辑：对不起，我已经审核并更正了我的公式。 由于双算术的精度误差，对于少数边界情况，结果可能是不正确的。 所以它仍然需要一些“voodo魔法”。 第二行处理这些情况并产生正确的结果。

Answer 7

如果您想混合汇编代码以获得最佳性能。 这是你在C＃中的表现。

首先是使支持代码成为可能：

 using System.Runtime.InteropServices; using System.Runtime.CompilerServices; using static System.Runtime.CompilerServices.MethodImplOptions; /// 
 Gets the position of the right most non-zero bit in a UInt32. 
 [MethodImpl(AggressiveInlining)] public static int BitScanForward(UInt32 mask) => _BitScanForward32(mask); /// 
 Gets the position of the left most non-zero bit in a UInt32. 
 [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(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)); } 

然后这是生成函数的程序集：

 [UnmanagedFunctionPointer(CallingConvention.Cdecl)] private delegate Int32 BitScan32Delegate(UInt32 inValue); private static BitScan32Delegate _BitScanForward32 = (new Func(() => { //IIFE BitScan32Delegate del = null; if(IntPtr.Size == 4){ del = GenerateX86Function( 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( //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(() => { //IIFE BitScan32Delegate del = null; if(IntPtr.Size == 4){ del = GenerateX86Function( 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( //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; }))(); 

为了生成程序集，我启动了一个新的VC ++项目，创建了我想要的函数，然后进入Debug – > Windows – > Disassembly。 对于编译器选项，我禁用内联，启用内在函数，优先快速代码，省略帧指针，禁用安全检查和SDL检查。 代码是：

 #include "stdafx.h" #include  #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; } 

Answer 8

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

Answer 9

在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)); } 

（来自http://aggregate.org/MAGIC/#Leading Zero Count ）

翻译成C＃对读者来说是一项微不足道的练习。

编辑

我给出链接的原因是，我不需要复制以下内容（再次在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); } 

Answer 10

计数前导零/查找第一组/位扫描反向是在OS和其他低级编程中需要的常见事情，大多数硬件支持clz以形成单周期指令。 大多数c / c ++编译器都有一个内在的编译器。

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

大多数硬件和编译器也有计数尾随零，弹出计数/位数/计数，奇偶校验，bswap /翻转endien，以及其他几个夸张但非常有用的bit twiddling操作。

Answer 11

使用预先计算的计数可以获得最佳性能

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

Answer 12

整数没有前导零，也不支持32位数。 话虽这么说，您应该能够通过将整数转换为字符串并检查长度来创建一个函数来执行此操作：

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