De Bruijn算法二进制数位计数64位C＃ [英] De Bruijn algorithm binary digit count 64bits C#
问题描述
Im使用De Bruijn算法来发现大数字（最多64位）具有的二进制数字位数。
例如：
- 1022的二进制数字为10位。
- 130二进制数字为8位。
我发现使用基于De Bruijn的表查找功能可以计算出比传统方法（power，square，...）快了100倍。 ）。
根据和他的资源< a>。他回答的问题是如何找到两个力量的log2。
比特twiddling网站说，简单的乘法+ shift只有工作如果你知道v是2的幂。否则，您需要先向下舍入到下一次方二：： p>
static readonly int [] bitPatternToLog2 = new int [64] {
0，//如果你想要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;
//在这一点上，你也可以使用popcount查找设置位的数量。
//这可能比查找表快，因为你阻止
//潜在缓存未命中
if（v ==（ulong）-1）return 64;
v ++;
return MultiplyDeBruijnBitPosition2 [（ulong）（v * multiplicator）> 58];
}
这里有一个更大的查找表，避免了分支和一个额外的。我使用随机搜索找到了魔法数字。
static readonly int [] bitPatternToLog2 = new int [128] {
0，//如果你想要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， 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， 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 ，并考虑使用 MSR 汇编指令如果您使用x86（_64 ）。它给你最重要的设置位的索引，这是你需要的。
Im using the "De Bruijn" Algorithm to discover the number of digits in binary that a big number (up to 64bits) has.
For example:
- 1022 has 10 digits in binary.
- 130 has 8 digits in binary.
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, ...).
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
};
(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];
}
But the c# compiler doesnt allow me to use "0x022fdd63cc95386dull" because it overflows 64bits. And i have to use "0x022fdd63cc95386d" instead.
Using those codes. The problem is that i am not getting the correct result for the input given.
For example, doing 1.000.000 calculations of the number: 17012389719861204799 (64bits used) This is the result:
- Using pow2 method i get the result 64 1 Million times in 1380ms.
- Using DeBruijn method i get the result 40 1 Million times in 32ms. (Dont know why 40)
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 and benchmarks of different solutions
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).
For example:
- 1024 has 11 binary digits. (2^10+1) or (log2[1024]+1)
- 9223372036854775808 has 64 binary digits. (2^63+1) or (log2[2^63]+1)
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).
Here, Niklas B., Jim Mischel, and Spender brought differents methods to make this faster.
- 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)
Testing this Methods with a CPU Q6600 overclocked to 3Ghz using Windows 7 (64bits) Gives the following results.
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.
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.
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];
}
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.
这篇关于De Bruijn算法二进制数位计数64位C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
