De Bruijn算法二进制数字计数64位C#

Question

我使用"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百万次.(不知道为什么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版本最快.

非常感谢你们所有人,你们对我帮助很大.我希望这对你也有帮助.

Answer 1

你应该再次检查R.. 的答案和他的资源。他回答的问题是如何求2 的幂的 log2 。

bit 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];
}

如果您使用的是 x86(_64)，您绝对应该检查其他技巧来计算 log2并考虑使用汇编指令。MSR它为您提供最高有效设置位的索引，这正是您所需要的。