快速查找64位整数中设置最高和最低有效位的方法
StackOverflow上有很多关于此的问题。 很多 但是我找不到答案：
- 在C＃中工作
- 适用于64位整数（而不是32位）
比…快：
private static int Obvious(ulong v) { int r = 0; while ((v >>= 1) != 0) { r++; } return r; } 甚至
int r = (int)(Math.Log(v,2));
我在这里假设一个64位Intel CPU。
一个有用的参考是Bit Hacks页面 ，另一个是fxtbook.pdf。然而，虽然这些提供了解决问题的有用方向，但它们没有给出准备好的答案。
我正在使用一个可重用的函数， 它只能为C＃执行与_BitScanForward64和_BitScanReverse64类似的操作。
根据我的评论，这是C＃中的一个函数，用于计算针对64位整数修改的前导零位。
public static UInt64 CountLeadingZeros(UInt64 input) { if (input == 0) return 64; UInt64 n = 1; if ((input >> 32) == 0) { n = n + 32; input = input << 32; } if ((input >> 48) == 0) { n = n + 16; input = input << 16; } if ((input >> 56) == 0) { n = n + 8; input = input << 8; } if ((input >> 60) == 0) { n = n + 4; input = input << 4; } if ((input >> 62) == 0) { n = n + 2; input = input << 2; } n = n - (input >> 63); return n; }
在问题中链接的Bit Hacks页面上描述的其中一种方法是利用De Bruijn序列 。 不幸的是，这个页面没有给出所述序列的64位版本。 这个有用的页面解释了如何构造De Bruijn序列，并且这个序列给出了用C ++编写的序列生成器的示例。 如果我们调整给定的代码，我们可以生成多个序列，其中一个序列在下面的C＃代码中给出：
public static class BitScanner { private const ulong Magic = 0x37E84A99DAE458F; private static readonly int[] MagicTable = { 0, 1, 17, 2, 18, 50, 3, 57, 47, 19, 22, 51, 29, 4, 33, 58, 15, 48, 20, 27, 25, 23, 52, 41, 54, 30, 38, 5, 43, 34, 59, 8, 63, 16, 49, 56, 46, 21, 28, 32, 14, 26, 24, 40, 53, 37, 42, 7, 62, 55, 45, 31, 13, 39, 36, 6, 61, 44, 12, 35, 60, 11, 10, 9, }; public static int BitScanForward(ulong b) { return MagicTable[((ulong) ((long) b & -(long) b)*Magic) >> 58]; } public static int BitScanReverse(ulong b) { b |= b >> 1; b |= b >> 2; b |= b >> 4; b |= b >> 8; b |= b >> 16; b |= b >> 32; b = b & ~(b >> 1); return MagicTable[b*Magic >> 58]; } }
我还将序列生成器的C＃端口发布到github
在这里可以找到De Bruijn序列覆盖的问题中未提及的另一篇相关文章。