德布鲁因算法二进制数字计数64位C＃ [英] De Bruijn algorithm binary digit count 64bits C#

问题描述

即时通讯使用的德布鲁因算法发现的二进制数字的数个大号码（最多64位）了。

Im using the "De Bruijn" Algorithm to discover the number of digits in binary that a big number (up to 64bits) has.

例如：

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

我发现，使用基于德布鲁因查表给我计算这个X100倍，比传统的方式（功率，正方形，...）。

I found that using a table lookup based on De Bruijn give me the power to calculate this x100 times faster than conventional ways (power, square, ...).

根据本网站，2 ^ 6的表来计算64位数字。这将表暴露在c＃

According to this website, 2^6 has the table to calculate the 64 bits numbers. this would be the table exposed in 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数量。

(I dont know if i brought the table from that website correctly) Then, based on the R.. comment here. I should use this to use the table with the input uint64 number.

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

但C＃编译器的犯规让我用 0x022fdd63cc95386dull ，因为它溢出64位。我必须用 0x022fdd63cc95386d 来代替。

But the c# compiler doesnt allow me to use "0x022fdd63cc95386dull" because it overflows 64bits. And i have to use "0x022fdd63cc95386d" instead.

使用这些codeS。问题是，我没有得到正确的结果对于给定的输入。

Using those codes. The problem is that i am not getting the correct result for the input given.

例如，在做1.000.000计算的数量： 17012389719861204799（64位用）这是结果：

For example, doing 1.000.000 calculations of the number: 17012389719861204799 (64bits used) This is the result:

• 使用POW2方法，我得到的结果是64 100万次的1380ms。
• 使用DeBruijn方法，我得到的结果是40 100万次的为32ms。 （不知道为什么40）

我试着去理解德布鲁因是如何工作的，以及如何解决这一问题，并创建一个最终的code对C＃来计算达64位数字。

Im trying to understand how "De Bruijn" works, and how can i fix this and create a final code for c# to calculate up to 64bits numbers.

UDPATE 和不同的解决方案的基准

UDPATE and benchmarks of different solutions

我一直在寻找最快的算法，得到的位数的二进制文件，64位的无符号给定数量在C＃（被称为ULONG）。

I was looking for the fastest algorithm to get the number of digits in binary that a unsigned given number of 64bits has in c# (known as ulong).

例如：

• 在1024有11个二进制数字。 （2 ^ 10 + 1）或（LOG2 [1024] 1）
• 9223372036854775808有64个二进制数字。 （2 ^ 63 + 1）或（LOG2 [2 ^ 63] 1）

2，方传统的力量是极其缓慢。和公正的10000计算，需要1500毫秒才能得到答案。 （100M计算需要时间）。

The conventional power of 2 and square is extremely slow. and just for 10000 calculations it needs 1500ms to get the answer. (100M calculations needs hours).

下面，尼克拉斯·B. ，的吉姆·米契尔和富豪带型动物的方法，使这种速度更快。

Here, Niklas B., Jim Mischel, and Spender brought differents methods to make this faster.

• SIMD和SWAR技术//由富豪（这里答）提供
• De_Bruijn Splited 32位//由吉姆·米契尔（这里答）
提供
• De_Bruijn 64位版本//由尼克拉斯·B。（这里答）
提供
• De_Bruijn 128位版本//也由尼克拉斯·B。（这里答）
提供

• SIMD and SWAR Techniques //Provided by Spender (Answer here)
• De_Bruijn Splited 32bits //Provided by Jim Mischel (Answer here)
• De_Bruijn 64bits version //Provided by Niklas B. (Answer here)
• De_Bruijn 128bits version //Also provided by Niklas B. (Answer here)

这个测试方法与CPU Q6600超频到3GHz使用Windows 7（64位）提供了以下结果。

Testing this Methods with a CPU Q6600 overclocked to 3Ghz using Windows 7 (64bits) Gives the following results.

正如你所看到的，它只需几秒钟的时间找到正确的请求给出亿，是De_Bruijn 128位的版本是最快的。

As you can see, it takes just a few seconds to find correctly 100,000,000 of request given, being De_Bruijn 128bits version the fastest.

非常感谢你们所有的人，你帮了我很多与此有关。我希望这可以帮助你。

Thanks a lot to all of you, you help me a lot with this. I hope this helps you too.

推荐答案

您应该检查 - [R ..的答案和他的资源了。这个问题，他回应是如何找到LOG2对于 2的幂

You should check R..'s answer and his resource again. The question that he responded to was how to find the log2 for powers of two.

该位摆弄网站说，简单的乘法+只是转移作品如果你知道，v是2的幂。否则，您必须四舍五入到两个先下一功率：

The bit twiddling website says that the simple multiplication + shift only works "If you know that v is a power of 2". Otherwise you need to round up to the next power of two first:

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

下面是一个版本有较大的查找表，避免了分公司和一个加法。我发现了一个神奇的数字使用随机搜索。

Here is a version with a larger lookup table that avoids the branch and one addition. I found the magic number using random search.

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 并考虑使用在<一个href="http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html"相对=nofollow> MSR 组件，如果你是在x86（_64）指令。它给你最显著设置位的索引，而这正是你所需要的。

You should definitely check other tricks to compute the log2 and consider using the MSR assembly instruction if you are on x86(_64). It gives you the index of the most significant set bit, which is exactly what you need.

这篇关于德布鲁因算法二进制数字计数64位C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！