如何计算 a 中的前导零Int32？所以我想做的是编写一个函数，如果我的输入是 2，它返回 30，因为在二进制中我有000...0000000000010.
user1310957
问问题
13846 次
15 回答
26
注意使用 dotnet core >=3.0？看这里。
我们以数字 20 为例。可以用二进制表示如下：
00000000000000000000000000010100
首先，我们通过对自身进行右移和按位或运算，将最高有效位“涂抹”在较低位位置上。
00000000000000000000000000010100
or 00000000000000000000000000001010 (right-shifted by 1)
is 00000000000000000000000000011110
然后
00000000000000000000000000011110
or 00000000000000000000000000000111 (right-shifted by 2)
is 00000000000000000000000000011111
在这里，因为它是一个小数字，我们已经完成了这项工作，但是通过 4、8 和 16 位的移位继续该过程，我们可以确保对于任何 32 位数字，我们已经设置了所有位0 到原数的 MSB 到 1。
现在，如果我们计算“拖尾”结果中 1 的数量，我们可以简单地从 32 中减去它，剩下的就是原始值中前导零的数量。
我们如何计算整数中设置的位数？这个页面有一个神奇的算法可以做到这一点（“ a variable-precision SWAR algorithm to perform a tree reduction ”......如果你明白了，你比我聪明！），它转换为 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);
}
通过将这个方法与我们上面的“smearing”方法内联，我们可以生成一个非常快速、无循环和无条件的方法来计算整数的前导零。
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
}
于 2012-05-03T21:06:34.667 回答
7
如果您想混合汇编代码以获得最佳性能。这是在 C# 中执行此操作的方法。
首先是使之成为可能的支持代码：
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));
}
然后是生成函数的程序集：
[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;
}))();
为了生成程序集，我开始了一个新的 VC++ 项目，创建了我想要的函数，然后转到 Debug-->Windows-->Disassembly。对于编译器选项，我禁用了内联、启用了内在函数、偏爱快速代码、省略了帧指针、禁用了安全检查和 SDL 检查。代码是：
#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;
}
于 2017-11-01T06:37:11.917 回答
7
在 .NET Core 3.0 中有BitOperations。LeadingZeroCount ()和BitOperations。TrailingZeroCount ()直接映射到 x86 的 LZCNT/BSR 和 TZCNT/BSF。因此，目前它们将是最有效的解决方案
于 2020-04-17T15:17:04.867 回答
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.
*
* <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;
}
于 2015-08-27T07:03:12.750 回答
3
试试这个：
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);
}
于 2012-05-03T21:42:22.630 回答
2
这里有一些复杂的答案。这个怎么样？
private int LeadingZeroes(int value)
{
return (32 - (Convert.ToString(value, 2).Length));
}
虽然现在我猜测负数可能存在一些问题，而这种类型的解决方案可能会出现一些问题。
于 2012-05-03T21:08:08.130 回答
2
如果您只想模拟 Lzcnt 指令，您可以这样做（它给出 32 表示零值）：
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);
}
如果您需要知道存储特定值需要多少位，最好是：
1+((int)Math.Log(value, 2)&int.MaxValue)
上面给出了一个零值——因为您实际上需要一位来存储零。
但这些仅适用于 uint 而不适用于 ulong。Double （这是 Log 方法参数）没有足够的精度来存储 ulong 直到最低有效位，因此(double)0xFFFFFFFFFFFFFF与(double)0x100000000000000.
但是在 .Net Core 3.0 中，我们终于有了最新最好的 Lzcnt 指令。因此，如果只有System.Runtime.Intrinsics.X86.Lzcnt.IsSupported（System.Runtime.Intrinsics.X86.Lzcnt.X64.IsSupported对于 ulong），那么您可以使用System.Runtime.Intrinsics.X86.Lzcnt.LeadingZeroCount(value)（System.Runtime.Intrinsics.X86.Lzcnt.X64.LeadingZeroCount(value)对于 ulong）。
但是有了 .Net Core 3.0，我们终于有了System.Numerics.BitOperations.LeadingZeroCount@phuclv 已经提到的最新和最棒的版本。
于 2019-10-06T17:00:40.463 回答
0
在 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);
}
于 2012-05-03T21:03:03.210 回答
0
private int GetIntegerOffsetLength(int value)
{
return (32 - (Convert.ToString(value, 2).Length);
}
于 2012-05-03T21:07:51.833 回答
0
来吧，伙计们，不要再问“为什么要这样做或那样”。回答是否可以或继续。计算前导零是许多问题（例如压缩算法）中的常见任务。甚至还有专门用于此的 x86 硬件指令（clz、bsr）。不幸的是，您不能在 C# 中使用这些硬件指令，因为（尚）不支持内在函数。我想转换成字符串是个笑话。
int 的二进制表示具有非常明确的界限。事实上，在 C# 中，int 只是 Int32 的别名。正如其名称所暗示的那样，“Int32”始终是 32 位有符号整数，即使您为 x64 编译项目也是如此。
而且你不需要一些特殊的巫术魔法来计算前导零：这是一个简单的数学解决方案：
这里“x”是你的 int (Int32)：
int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);
编辑：对不起，我已经审查并更正了我的公式。由于双重算术的精度误差，对于少数边界情况，结果可能不正确。所以它仍然需要一些“巫毒魔法”。第二行处理这些情况并产生正确的结果。
于 2012-07-10T17:07:35.923 回答
0
我认为最好的选择是上面的 spender 的帖子。但是，如果有人正在寻找轻微的性能提升，可以使用以下方法..（注意：在我机器上的基准测试中它只快 2%）
这个通过将浮点数转换为整数然后抓取指数位来工作。
[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;
}
这也可以扩展到 Int64 版本......
[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;
}
注意：在浮点数中使用指数的想法来自SPWorley 3/22/2009。谨慎使用生产代码，因为这在非小端架构上会失败。
以下是 Floor-Log2 的一些基准 - 这几乎相同：https ://github.com/SunsetQuest/Fast-Integer-Log2 ）
于 2019-10-20T21:36:18.960 回答
-1
计数前导零/查找第一个设置/位扫描反向是操作系统和其他低级编程中最常见的事情，大多数硬件支持 clz 以形成单周期指令。并且大多数 c/c++ 编译器都有一个固有的编译器。
http://en.wikipedia.org/wiki/Find_first_set
大多数硬件和编译器也有计数尾随零、弹出计数/位计数/计数、奇偶校验、bswap/flip endien 和其他几个夸夸其谈但非常有用的位旋转操作。
于 2014-02-07T21:50:48.317 回答
-2
32 - Convert.ToString(2,2).Count()
于 2012-05-03T21:08:29.067 回答
-2
您可以使用预先计算的计数获得最佳性能
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);
}
}
于 2013-09-08T18:29:05.063 回答
-4
整数没有前导零，也不支持 32 位数字。话虽如此，您应该能够通过将整数转换为字符串并检查长度来创建一个函数来执行此操作：
private int GetIntegerOffsetLength(int value)
{
//change 32 to whatever your upper bound is
return (32 - (value.ToString().Length + 1));
}
于 2012-05-03T21:03:46.113 回答