AnT*_*AnT 30 algorithm bit-manipulation logarithm discrete-mathematics
我正在查看条目在O(lg(N))操作中查找N位整数的日志基数2,并使用Bit Twiddling hacks 进行乘法和查找.
我可以很容易地看到该条目中的第二个算法是如何工作的
static const int MultiplyDeBruijnBitPosition2[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
计算n = log2 v在哪里v知道2的幂.在这种情况下0x077CB531是一个普通的De Bruijn序列,其余的是显而易见的.
但是,该条目中的第一个算法
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
看起来对我来说有点棘手.我们首先捕捉v到更接近的更大2^n - 1值.2^n - 1然后将该值乘以0x07C4ACDD,在这种情况下,其行为与先前算法中的DeBruijn序列的行为相同.
我的问题是:我们如何构建这个神奇的0x07C4ACDD序列？即我们如何构造一个序列,当乘以一个2^n - 1值时可用于生成唯一索引？对于2^n乘数来说,它只是一个普通的De Bruijn序列,正如我们在上面所看到的,所以很明显从哪里来0x077CB531.但2^n - 1乘数0x07C4ACDD怎么样？我觉得我在这里遗漏了一些明显的东西.
PS为了澄清我的问题:我并不是在寻找生成这些序列的算法.我对一些或多或少的琐碎属性(如果存在的话)更感兴趣,这些属性使0x07C4ACDD我们希望它工作.对于0x077CB531使其工作的属性非常明显:它包含序列中"存储"的所有5位组合,具有1位步进(这基本上是De Bruijn序列).
的0x07C4ACDD,而另一方面,是不是本身就是一个德布鲁因序列.那么,他们在构建时的目标是什么0x07C4ACDD(除了非建设性的"它应该使上述算法工作")？有人确实以某种方式提出了上述算法.所以他们可能知道这种方法是可行的,并且存在适当的序列.他们怎么知道的？
例如,如果我要为任意构造算法v,我会这样做
v |= v >> 1;
v |= v >> 2;
...
第一.然后,我只是做++v转v成2的幂(假设它不会溢出).然后我会应用第一个算法.最后我会做到--r最后的答案.然而,这些人设法优化它:他们通过改变乘数和重新排列表来消除前导++v和尾随--r步骤.他们怎么知道这是可能的？这种优化背后的数学是什么？
Fri*_*igo 15
阶数n超过k个码元(并且k ^ N长度的)的德布鲁因序列具有每个可能的N长度的词出现在它作为连续的字符,它们中的一些与环状缠绕的性质.例如,在k = 2,n = 2的情况下,可能的单词是00,01,10,11,并且De Bruijn序列是0011.00,01,11出现在其中,10表示包裹.这个属性自然意味着左移De Bruijn序列(乘以2的幂)并取其高n位导致两个乘法器的每个幂的唯一数.然后,您只需要一个查找表来确定它是哪一个.它的工作原理类似于数字,其数值小于2的幂,但在这种情况下,幻数不是De Bruijn序列,而是类比.定义属性简单地改变为"每个可能的n长度的单词出现为长度为n的前m个子序列的总和,mod 2 ^ n".此属性是算法工作所需的全部属性.他们只是使用这种不同类型的幻数来加速算法.我做得也好.
构建De Bruijn数的一种可能方法是生成De Bruijn图的哈密顿路径,维基百科提供了这种图的示例.在这种情况下,节点是2 ^ 5 = 32位整数,有向边是它们之间的过渡,其中过渡是左移,二进制或操作根据边的标签,0或1.是2 ^ n-1类型幻数的直接类比,它可能值得探索,但这不是人们通常构造这种算法的方式.
在实践中,您可能会尝试以不同的方式构造它,特别是如果您希望它以不同的方式运行.例如,在bit twiddling hacks页面上实现前导/尾随数量的零算法只能返回[0..31]中的值.它需要额外检查0的情况,它有32个零.此检查需要分支,并且在某些CPU上可能太慢.
我这样做的方式,我使用64元素查找表而不是32,生成随机幻数,并为每一个我建立了一个具有两个输入功率的查找表,检查其正确性(注入性),然后验证它所有32位数字.我继续,直到遇到一个正确的幻数.得到的数字不满足"出现每个可能的n长度单词"的属性,因为只出现33个数字,这对于所有33个可能的输入是唯一的.
穷尽的强力搜索听起来很慢,特别是如果好的魔术数字很少,但如果我们首先测试两个值的已知功率作为输入,则表格快速填充,拒绝速度快,拒绝率非常高.我们只需要在每个幻数后清除表格.本质上,我利用高拒绝率算法来构造幻数.
得到的算法是
int32 Integer::numberOfLeadingZeros (int32 x)
{
static int32 v[64] = {
32, -1, 1, 19, -1, -1, -1, 27, -1, 24, 3, -1, 29, -1, 9, -1,
12, 7, -1, 20, -1, -1, 4, 30, 10, -1, 21, -1, 5, 31, -1, -1,
-1, -1, 0, 18, 17, 16, -1, -1, 15, -1, -1, -1, 26, -1, 14, -1,
23, -1, 2, -1, -1, 28, 25, -1, -1, 13, 8, -1, -1, 11, 22, 6};
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x *= 0x749c0b5d;
return v[cast<uint32>(x) >> 26];
}
int32 Integer::numberOfTrailingZeros (int32 x)
{
static int32 v[64] = {
32, -1, 2, -1, 3, -1, -1, -1, -1, 4, -1, 17, 13, -1, -1, 7,
0, -1, -1, 5, -1, -1, 27, 18, 29, 14, 24, -1, -1, 20, 8, -1,
31, 1, -1, -1, -1, 16, 12, 6, -1, -1, -1, 26, 28, 23, 19, -1,
30, -1, 15, 11, -1, 25, 22, -1, -1, 10, -1, 21, 9, -1, -1, -1};
x &= -x;
x *= 0x4279976b;
return v[cast<uint32>(x) >> 26];
}
至于你如何知道他们的问题,他们可能没有.他们试验,试图改变一切,就像我一样.毕竟,2 ^ n-1输入可能工作而不是2 ^ n输入具有不同的幻数和查找表,这不是一大片想象力.
在这里,我制作了我的幻数生成器代码的简化版本.如果我们仅检查两个输入的功率,它会在5分钟内检查所有可能的幻数,找到1024个幻数.检查其他输入是没有意义的,因为无论如何它们都减少到2 ^ n-1形式.不构造表格,但一旦你知道了幻数,它就是微不足道的.
#include <Frigo/all>
#include <Frigo/all.cpp>
using namespace Frigo::Lang;
using namespace std;
class MagicNumberGenerator
{
public:
static const int32 log2n = 5;
static const int32 n = 1 << log2n;
static const bool tryZero = false;
MagicNumberGenerator () {}
void tryAllMagic ()
{
for( int32 magic = 0; magic < Integer::MAX_VALUE; magic++ ){
tryMagic(magic);
}
tryMagic(Integer::MAX_VALUE);
for( int32 magic = Integer::MIN_VALUE; magic < 0; magic++ ){
tryMagic(magic);
}
}
bool tryMagic (int32 magic)
{
// clear table
for( int32 i = 0; i < n; i++ ){
table[i] = -1;
}
// try for zero
if( tryZero and not tryInput(magic, 0) ){
return false;
}
// try for all power of two inputs, filling table quickly in the process
for( int32 i = 0; i < 32; i++ ){
if( not tryInput(magic, 1 << i) ){
return false;
}
}
// here we would test all possible 32-bit inputs except zero, but it is pointless due to the reduction to 2^n-1 form
// we found a magic number
cout << "Magic number found: 0x" << Integer::toHexString(magic) << endl;
return true;
}
bool tryInput (int32 magic, int32 x)
{
// calculate good answer
int32 leadingZeros = goodNumberOfLeadingZeros(x);
// calculate scrambled but hopefully injective answer
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x *= magic;
x = Integer::unsignedRightShift(x, 32 - log2n);
// reject if answer is not injective
if( table[x] != -1 ){
return table[x] == leadingZeros;
}
// store result for further injectivity checks
table[x] = leadingZeros;
return true;
}
static int32 goodNumberOfLeadingZeros (int32 x)
{
int32 r = 32;
if( cast<uint32>(x) & 0xffff0000 ){
x >>= 16;
r -= 16;
}
if( x & 0xff00 ){
x >>= 8;
r -= 8;
}
if( x & 0xf0 ){
x >>= 4;
r -= 4;
}
if( x & 0xc ){
x >>= 2;
r -= 2;
}
if( x & 0x2 ){
x >>= 1;
r--;
}
if( x & 0x1 ){
r--;
}
return r;
}
int32 table[n];
};
int32 main (int32 argc, char* argv[])
{
if(argc||argv){}
measure{
MagicNumberGenerator gen;
gen.tryAllMagic();
}
}