如何计算Int32中的前导零？所以我想要做的是写一个函数,如果我的输入Int32是2则返回30,因为在二进制中我有0000000000000010.
spe*_*der 19
我们以数字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
}
如果您想混入汇编代码以获得最佳性能。这是您在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;
}
在 .NET Core 3.0 中有BitOperations。LeadZeroCount ()和BitOperations。TrailingZeroCount ()直接映射到 x86 的 LZCNT/BSR 和 TZCNT/BSF。因此，目前它们将是最有效的解决方案
试试这个:
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);
}