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

Question

我正在使用“De Bruijn”算法来发现大数(最多 64 位)的二进制位数。

例如:

• 1022在二进制中有10位。
• 130在二进制中有8位。

我发现使用基于 De Bruijn 的表查找让我能够以比传统方法(幂、平方、...)快 100 倍的速度进行计算。

根据 this website , 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.. 评论 here .我应该使用它来使用带有输入 uint64 数字的表。

public static int GetLog2_DeBruijn(ulong v)
{
return MultiplyDeBruijnBitPosition2[(ulong)(v * 0x022fdd63cc95386dull) >> 58];
}

但 C# 编译器不允许我使用“0x022fdd63cc95386dull”，因为它会溢出 64 位。我必须改用“0x022fdd63cc95386d”。

使用这些代码。问题是我没有得到给定输入的正确结果。

例如，对数字进行 1.000.000 次计算:17012389719861204799(使用 64 位)这是结果:

• 使用 pow2 方法，我在 1380 毫秒内得到了 64 100 万次结果。
• 使用 DeBruijn 方法，我在 32 毫秒内得到了 40 100 万次结果。 (不知道为什么 40)

我试图了解“De Bruijn”的工作原理，以及如何解决此问题并为 C# 创建最终代码以计算最多 64 位数字。

UDPATE 和不同解决方案的基准

我一直在寻找最快的算法来获取在 C# 中给定的无符号 64 位数字的二进制位数(称为 ulong)。

例如:

• 1024 有 11 个二进制数字。 (2^10+1) 或 (log2[1024]+1)
• 9223372036854775808 有 64 个二进制数字。 (2^63+1) 或 (log2[2^63]+1)

2 和平方的常规幂非常慢。仅对于 10000 次计算，它需要 1500 毫秒才能得到答案。 (100M 计算需要数小时)。

在这里，Niklas B. , Jim Mischel , 和 Spender带来了不同的方法来加快速度。

• SIMD 和 SWAR 技术//由 Spender 提供(答案 here)
• De_Bruijn Splited 32bits//由 Jim Mischel 提供(答案 here)
• De_Bruijn 64 位版本//由 Niklas B 提供。(答案 here)
• De_Bruijn 128bits 版本//也由 Niklas B 提供。(答案 here )

使用 Windows 7(64 位)超频至 3Ghz 的 CPU Q6600 测试此方法给出以下结果。

如您所见，只需几秒钟即可正确找到给定的 100,000,000 个请求，是最快的 De_Bruijn 128 位版本。

非常感谢大家，你们在这方面帮了我很多。我希望这对你也有帮助。

Answer 1

你应该检查R..'s answer和 his resource再次。他回答的问题是如何找到 2 的幂 的 log2。

bit twiddling 网站说简单的乘法 + shift 只适用于“如果你知道 v 是 2 的幂”。否则你需要 round up to the next power of two第一:

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

这是一个具有更大查找表的版本，避免了分支和一次添加。我使用随机搜索找到了魔数(Magic Number)。

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

你绝对应该检查other tricks to compute the log2并考虑使用 MSR如果您使用的是 x86(_64)，请使用汇编指令。它为您提供了最高有效位的索引，这正是您所需要的。