De Bruijn算法二进制数字计数64位C＃
我使用“De Bruijn”算法来发现大数（最多64位）的二进制位数。
例如：
- 1022具有10位二进制数字。
- 130具有8位二进制数字。
我发现使用基于De Bruijn的表查找使我有能力比传统方式（功率，方形……）计算x100倍。
根据该网站 ，2 ^ 6具有用于计算64位数的表。 这将是c＃中暴露的表
static readonly int[] MultiplyDeBruijnBitPosition2 = new int[64] { 0,1,2,4,8,17,34,5,11,23,47,31,63,62,61,59, 55,46,29,58,53,43,22,44,24,49,35,7,15,30,60,57, 51,38,12,25,50,36,9,18,37,10,21,42,20,41,19,39, 14,28,56,48,33,3,6,13,27,54,45,26,52,40,16,32 }; （我不知道我是否正确地从该网站带来了桌子）然后，基于R ..评论在这里 。 我应该使用它来使用输入uint64号码的表。
public static int GetLog2_DeBruijn(ulong v) { return MultiplyDeBruijnBitPosition2[(ulong)(v * 0x022fdd63cc95386dull) >> 58]; }
但是c＃编译器不允许我使用“ 0x022fdd63cc95386dull ”，因为它溢出了64位 。 我必须使用“ 0x022fdd63cc95386d ”代替。
使用这些代码。 问题是我没有得到给定输入的正确结果。
例如，做1.000.000计算的数字：17012389719861204799（使用64位）这是结果：
- 使用pow2方法我在1380ms内得到64百万次的结果。
- 使用DeBruijn方法，我在32ms内得到结果40 1百万次。 （不知道为什么40）
我试图理解“De Bruijn”是如何工作的，我该如何解决这个问题并为c＃创建一个最终代码来计算高达64位的数字。
UDPATE和不同解决方案的基准
我一直在寻找最快的算法来获得二进制中的数字位数，这是无符号给定数量的64位在c＃中的数字（称为ulong）。
例如：
- 1024有11位二进制数字。 （2 ^ 10 + 1）或（log2 [1024] +1）
- 9223372036854775808有64位二进制数字。 （2 ^ 63 + 1）或（log2 [2 ^ 63] +1）
传统的2和平方功率非常慢。 只需10000次计算就需要1500ms才能得到答案。 （100M计算需要数小时）。
在这里， Niklas B. ， Jim Mischel和Spender带来了不同的方法来加快速度。
- SIMD和SWAR技术//由Spender提供（ 这里回答）
- De_Bruijn Spibited 32bits //由Jim Mischel提供（ 这里回答）
- De_Bruijn 64位版本//由Niklas B.提供（ 此处回答）
- De_Bruijn 128bits版本//也由Niklas B.提供（ 这里回答）
使用Windows 7（64位）将CPU Q6600超频至3Ghz测试此方法给出以下结果。
正如您所看到的，只需几秒钟即可找到正确的100,000,000请求，De_Bruijn 128bits版本最快。
非常感谢你们所有人，你们对我帮助很大。 我希望这对你也有帮助。
你应该再次检查R ..的答案和他的资源 。 他回答的问题是如何找到2的幂的log2。
这个位于twiddling的网站说，简单的乘法+移位仅适用于“如果你知道v是2的幂”。 否则你需要先完成下一个2的幂 ：
static readonly int[] bitPatternToLog2 = new int[64] { 0, // change to 1 if you want bitSize(0) = 1 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 }; // table taken from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator static readonly ulong multiplicator = 0x022fdd63cc95386dUL; public static int bitSize(ulong v) { v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v |= v >> 32; // at this point you could also use popcount to find the number of set bits. // That might well be faster than a lookup table because you prevent a // potential cache miss if (v == (ulong)-1) return 64; v++; return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >> 58]; }
这是一个具有更大查找表的版本，可以避免分支和一个添加。 我使用随机搜索找到了幻数。
static readonly int[] bitPatternToLog2 = new int[128] { 0, // change to 1 if you want bitSize(0) = 1 48, -1, -1, 31, -1, 15, 51, -1, 63, 5, -1, -1, -1, 19, -1, 23, 28, -1, -1, -1, 40, 36, 46, -1, 13, -1, -1, -1, 34, -1, 58, -1, 60, 2, 43, 55, -1, -1, -1, 50, 62, 4, -1, 18, 27, -1, 39, 45, -1, -1, 33, 57, -1, 1, 54, -1, 49, -1, 17, -1, -1, 32, -1, 53, -1, 16, -1, -1, 52, -1, -1, -1, 64, 6, 7, 8, -1, 9, -1, -1, -1, 20, 10, -1, -1, 24, -1, 29, -1, -1, 21, -1, 11, -1, -1, 41, -1, 25, 37, -1, 47, -1, 30, 14, -1, -1, -1, -1, 22, -1, -1, 35, 12, -1, -1, -1, 59, 42, -1, -1, 61, 3, 26, 38, 44, -1, 56 }; static readonly ulong multiplicator = 0x6c04f118e9966f6bUL; public static int bitSize(ulong v) { v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v |= v >> 32; return bitPatternToLog2[(ulong)(v * multiplicator) >> 57]; }
你应该检查其他技巧来计算log2 ，如果你使用的是x86（_64），请考虑使用MSR汇编指令。 它为您提供了最重要的设置位的索引，这正是您所需要的。
在仔细阅读各种 比特信息之后，我就是这样做的……不知道它如何叠加在DeBruijn旁边，但应该比使用功率快得多。
ulong NumBits64(ulong x) { return (Ones64(Msb64(x) - 1ul) + 1ul); } ulong Msb64(ulong x) { //http://aggregate.org/MAGIC/ x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); x |= (x >> 32); return(x & ~(x >> 1)); } ulong Ones64(ulong x) { //https://chessprogramming.wikispaces.com/SIMD+and+SWAR+Techniques const ulong k1 = 0x5555555555555555ul; const ulong k2 = 0x3333333333333333ul; const ulong k4 = 0x0f0f0f0f0f0f0f0ful; x = x - ((x >> 1) & k1); x = (x & k2) + ((x >> 2) & k2); x = (x + (x >> 4)) & k4; x = (x * 0x0101010101010101ul) >> 56; return x; }
当我稍微调查一下32位时，DeBruijn序列方法是迄今为止最快的。 请参阅https://stackoverflow.com/a/10150991/56778
你可以为64位做什么将数字分成两个32位值。 如果高32位非零，则对其运行DeBruijn计算，然后加上32.如果高32位为零，则在低32位上运行DeBruijn计算。
像这样的东西：
int NumBits64(ulong val) { if (val > 0x00000000FFFFFFFFul) { // Value is greater than largest 32 bit number, // so calculate the number of bits in the top half // and add 32. return 32 + GetLog2_DeBruijn((int)(val >> 32)); } // Number is no more than 32 bits, // so calculate number of bits in the bottom half. return GetLog2_DeBruijn((int)(val & 0xFFFFFFFF)); } int GetLog2_DeBruijn(int val) { uint32 v = (uint32)val; int r; // result goes here static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; return r; }
编辑：不建议使用此解决方案，因为它需要分支为零。
在阅读了Niklas B的答案之后，我花了几个小时来研究这个，并且意识到所有魔法乘法器必须在最后n个，以便适合64个元素的查找表（我没有必要的知识来解释原因） 。
所以我使用该答案提到的完全相同的生成器来查找最后一个序列 ，这里是C＃代码：
// used generator from http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator static readonly byte[] DeBruijnMSB64table = new byte[] { 0 , 47, 1 , 56, 48, 27, 2 , 60, 57, 49, 41, 37, 28, 16, 3 , 61, 54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4 , 62, 46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45, 25, 39, 14, 33, 19, 30, 9 , 24, 13, 18, 8 , 12, 7 , 6 , 5 , 63, }; // the cyclc number has to be in the last 16th of all possible values // any beyond the 62914560th(0x03C0_0000) should work for this purpose const ulong DeBruijnMSB64multi = 0x03F79D71B4CB0A89uL; // the last one public static byte GetMostSignificantBit(this ulong value) { value |= value >> 1; value |= value >> 2; value |= value >> 4; value |= value >> 8; value |= value >> 16; value |= value >> 32; return DeBruijnMSB64table[value * DeBruijnMSB64multi >> 58]; }