计算 Int32 中的前导零
本文关键字：Int32 计算 | 更新日期: 2023-09-27 18:33:11
如何计算Int32中的前导零？所以我想做的是编写一个函数，如果我的输入是 30，则返回 2，因为在二进制文件中我有 000...0000000000010 .
注意 使用 dotnet core>=3.0？看这里。
让我们以数字 20 为例。它可以用二进制表示如下：
00000000000000000000000000010100
首先，我们通过右移和按位OR在自身上"涂抹"较低位位置上的最有效位。
00000000000000000000000000010100
or 00000000000000000000000000001010 (right-shifted by 1)
is 00000000000000000000000000011110
然后
00000000000000000000000000011110
or 00000000000000000000000000000111 (right-shifted by 2)
is 00000000000000000000000000011111
在这里，因为它是一个小数字，我们已经完成了这项工作，但是通过继续 4、8 和 16 位的移位过程，我们可以确保对于任何 32 位数字，我们已将原始数字的 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
}
在.NET Core 3.0中，有BitOperations。LeadingZeroCount(( 和 BitOperations。TrailingZeroCount((，如果可用，它直接映射到硬件指令，例如x86上的LZCNT/BSR和TZCNT/BSF，或ARM上的CLZ/CTZ。因此，目前它们应该是最有效的解决方案
如果您想混合汇编代码以获得最佳性能。 下面介绍如何在 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++项目，创建了我想要的函数，然后转到调试-->Windows-->反汇编。对于编译器选项，我禁用了内联，启用了内部函数，偏爱快速代码，省略了帧指针，禁用了安全检查和 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;
}
查看 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;
}
试试这个：
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);
}
如果你只想模拟 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。双精度(即 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已经提到的那样。
这里有一些复杂的答案。怎么样？
private int LeadingZeroes(int value)
{
return (32 - (Convert.ToString(value, 2).Length));
}
虽然现在我猜负数可能存在一些问题，但这种类型的解决方案不存在。
在 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);
}
来吧伙计们，不要再问"你为什么要做这个或那个"。如果可以，请回答，或者继续。计算前导零是许多问题(例如压缩算法(中的常见任务。甚至还有专用于此的x86硬件指令(clz，bsr(。遗憾的是，您无法在 C# 中使用这些硬件指令，因为尚不支持内部函数。我想转换为字符串是一个笑话。
int 的二进制表示具有非常明确的边界。事实上，在 C# 中，int 只是 Int32 的别名。正如其 namge 所暗示的那样，"Int32"始终是 32 位有符号整数，即使您为 x64 编译项目也是如此。
而且你不需要一些特殊的巫术来计算前导零：这是有效的简单数学解决方案：
这里的"x"是你的int(Int32(：
int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d));
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31);
编辑：对不起，我已经审查并更正了我的公式。由于双算术的精度误差，结果可能会对于少数边界情况不正确。所以它仍然需要一些"巫术"。第二行处理这些情况并生成正确的结果。
我认为最好的选择是上面的花钱者的帖子。 但是，如果有人正在寻找轻微的性能提升，则可以使用以下方法。 (注意：在我的机器上的基准测试中，它只快了 2%(
这个通过将浮点数转换为 int 然后抓取指数位来工作。
[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(
计数前导零/查找第一组/位扫描反向是操作系统和其他低级编程中常见的事情，大多数硬件都支持CLZ以单周期指令的形式出现。大多数 c/c++ 编译器都有一个固有的编译器。
http://en.wikipedia.org/wiki/Find_first_set
此外，大多数硬件和编译器还具有计数尾随零，pop count/bit count/count 1，Parity，BSWAP/Flip Endien以及其他一些夸克但非常有用的位抖动操作。
您可以使用预先计算的计数获得最佳性能
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);
}
}
32 - Convert.ToString(2,2).Count()
整数没有前导零，也不支持 32 位数字。话虽如此，您应该能够通过将整数转换为字符串并检查长度来创建函数来执行此操作：
private int GetIntegerOffsetLength(int value)
{
//change 32 to whatever your upper bound is
return (32 - (value.ToString().Length + 1));
}