De Bruijn 算法二进制数字计数 64bits C# [英] De Bruijn algorithm binary digit count 64bits C#
问题描述
我使用De Bruijn"算法来发现一个大数(最多 64 位)的二进制位数.
例如:
- 1022 有 10 位二进制.
- 130 有 8 位二进制数字.
我发现使用基于 De Bruijn 的表查找使我能够以比传统方法(幂、平方等)快 100 倍的速度计算此值.
根据和 他的资源.他回答的问题是如何找到二的幂的log2.
bit twiddling 网站说简单的乘法 + 移位仅适用于如果您知道 v 是 2 的幂".否则，您需要先四舍五入到下一个二的幂:
static readonly int[] bitPatternToLog2 = new int[64] {0,//如果你想要 bitSize(0) = 1 就改成 11, 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};//表格取自 http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator静态只读 ulong 乘法器 = 0x022fdd63cc95386dUL；公共静态 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) 返回 64；v++;return MultiplyDeBruijnBitPosition2[(ulong)(v * multiplicator) >>58];}这是一个具有更大查找表的版本，它避免了分支和一次添加.我使用随机搜索找到了幻数.
static readonly int[] bitPatternToLog2 = new int[128] {0,//如果你想要 bitSize(0) = 1 就改成 148, -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};静态只读 ulong 乘数 = 0x6c04f118e9966f6bUL；公共静态 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 算法二进制数字计数 64bits C#的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
