哇,看起来有一个关于C#的问题最近还没有被解决。
其他评论者已经正确地指出,像_BitScanForward这样的内置函数本质上不是函数,而是编译器将特定平台指令注入到目标代码中的标记。在高级语言中无法模拟内置函数(除非您愿意支付抽象代价)。
然而,好消息是,从.Net Core 3.0开始,JIT支持一些硬件平台的内置函数。
对于_BitScanForward,您可以使用System.Runtime.Intrinsics.X86.Bmi1.TrailingZeroCount。
注意:在使用之前,请不要忘记检查Bmi1.IsSupported
,否则代码会在运行时失败。
您还可以通过使用ARM的ffs内置函数在ARM(.Net 5.0+)上获得良好的执行速度:
public int ArmBitScanForward(int x)
=> 32 − System.Runtime.Intrinsics.Arm.ArmBase.LeadingZeroCount(x & −x);
public int ArmBitScanForward(long x)
=> 64 − System.Runtime.Intrinsics.Arm.ArmBase.Arm64.LeadingZeroCount(x & −x);
如果没有任何平台可用,您将不得不使用位运算技巧,如de-Bruijun序列:
for i from 0 to 31: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // table [0..31] initialized
function ctz5 (x)
return table[((x & -x) * 0x077CB531) >> 27]
(来自https://en.wikipedia.org/wiki/Find_first_set)
根据任务限制,我会在运行时选择不同的算法选择策略。每次调用分支可能会破坏所有效率。最有效的方法是在更高的级别上进行分支——即在运行时有三个版本的代码可供选择。
自动化代码生成的简单方法是将代码放入通用形式的参数化位处理类型中:
public interface IBitScanner
{
int BitScanForward(int x);
}
public int MyFunction<T>(int[] data)
where T: new, IBitScanner
{
var s=0;
var scanner = new T();
foreach(var i in data)
s+= scanner.BitScanForward(i);
return s;
}
然后我们定义了几个结构体来实现扫描器:
public struct BitScannerX86: IBitScanner
{
public int BitScanForward(int x)
=> unchecked((int)System.Runtime.Intrinsics.X86.Bmi1.TrailingZeroCount((uint)x));
}
public struct BitScannerArm: IBitScanner
{
public int BitScanForward(int x)
=> 32 − System.Runtime.Intrinsics.Arm.ArmBase.LeadingZeroCount(x & −x);
}
public struct BitScanner: IBitScanner
{
private static int[] _table = InitTable();
private static int[] InitTable()
{
var table = new int[32];
for(var i=0; i<table.Length; i++)
table[i] = ( 0x077CB531 * ( 1 << i ) ) >> 27;
return table;
}
public int BitScanForward(int x)
=> _table[((x & -x) * 0x077CB531) >> 27]
}
现在,每当我们需要一个特定于平台的MyFunction版本时,我们通过
MyFunction<BitScannerArm>
来实现。作为结构体,类型参数强制JIT生成特定代码,而不是喜欢虚拟调用的通用代码。
然后,由于在JIT时间T已知,对BitScanForward的调用被内联,并最终注入到循环中适当的内部函数。
根据MyFunction任务的大小,此版本的MyFunction可能保存到委托中,成为接口的一部分,或成为实现接口的结构体的一部分,以将技巧重复一级。
请注意,原始问题并未考虑跨平台兼容性,因为_BitScanForward是仅限英特尔的指令。
这在C ++世界中编译可执行文件针对特定的OS&HW组合时可能是可以的;当代的受管理代码如Java / .Net有机会在任何地方执行。