Wow, looks like there is a question on C# that haven't yet been covered with the recent improvements.
Other commenters have properly noted that the intrinsics like _BitScanForward are not functions per se, those are rather markers for the compiler to inject a specific platform instruction into the object code. It is impossible to emulate an intrinsic in a high-level language (unless you're willing to pay an abstraction penalty).
However, good news is that starting with .Net Core 3.0 the JIT does support the intrinsics for a number of hardware platforms.
For the _BitScanForward you might use System.Runtime.Intrinsics.X86.Bmi1.TrailingZeroCount.
Caveat: Don't forget to check for Bmi1.IsSupported before using, otherwise the code would fail at runtime.
You could also get a decent execution speed on ARM (.Net 5.0+) by using their ffs intrinsics:
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);
If neither platform is present, you would have to resort to the bit-twiddling hacks like de-Bruijun sequences:
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]
(taken from https://en.wikipedia.org/wiki/Find_first_set)
Depending on the task restrictions, I would choose across different strategies of the algorithm selection at runtime. Branching on each call is likely to kill all the efficiency. The most efficient way is to branch on a level higher - i.e. have three versions of your code to choose from at run time.
An easy way to automate codegen is to have your code in a generic from parameterized with a bit-handling type:
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;
}
Then we define a couple of structs implementing our scanner:
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]
}
Now whenever we need a platform-specific version of MyFunction, we do it via
MyFunction<BitScannerArm>. Being struct, the type parameter forces JIT to generate the specific code for it instead of a generic one fancying a virtual call.
Then, as the T is known at JIT time, the call to BitScanForward gets inlined, and ends up with the appropriate intrinsic injected into the loop.
Depending on the MyFunction task size, this version of MyFunction might be saved to a delegate, be part of an interface, or be part of a struct that implements an interface to repeat the trick one level higher.
Note that original question didn't bother with the cross-platform compatibility, as the _BitScanForward is an Intel-only instruction.
It was probably Ok in the C++ world of compiling an executable against a specific OS&HW combination; contemporary managed code like Java/.Net has a chance to be executed anywhere.
