algorithm - `2^n - 1` : how is it constructed? 的类 De Bruijn 序列

Question

我正在查看条目 Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup来自 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 序列？ IE。当乘以 2^n - 1 值时，我们如何构建可用于生成唯一索引的序列？对于 2^n 乘数，它只是一个普通的 De Bruijn 序列，正如我们在上面看到的，所以很明显 0x077CB531 来自哪里。但是 2^n - 1 乘数 0x07C4ACDD 呢？我觉得我在这里遗漏了一些明显的东西。

P.S. 澄清一下我的问题:我并不是真的在寻找一种算法来生成这些序列。我对使 0x07C4ACDD 按我们希望的方式工作的一些或多或少的琐碎属性(如果存在的话)更感兴趣。对于 0x077CB531，使其工作的属性非常明显:它包含序列中“存储”的所有 5 位组合，步进为 1 位(这基本上就是 De Bruijn 序列)。

另一方面，0x07C4ACDD 本身并不是 De Bruijn 序列。那么，在构造 0x07C4ACDD 时，他们的目标是什么属性(除了非构造性的“它应该使上述算法工作”之外)？确实有人以某种方式提出了上述算法。所以他们可能知道该方法是可行的，并且存在适当的顺序。他们怎么知道的？

例如，如果我要为任意 v 构建算法，我会这样做

v |= v >> 1;
v |= v >> 2;
...

首先。然后我将执行 ++v 将 v 转换为 2 的幂(假设它不会溢出)。然后我会应用第一个算法。最后我会执行 --r 以获得最终答案。然而，这些人设法对其进行了优化:他们简单地通过更改乘数和重新排列表格来消除了前导 ++v 和尾随 --r 步骤。他们怎么知道这是可能的？这种优化背后的数学原理是什么？

Answer 1

n 阶的 de Bruijn 序列超过 k 个符号(且长度为 k^n)具有一个属性，即每个可能的 n 长度单词在其中显示为连续字符，其中一些具有循环包装。比如在k=2,n=2的情况下，可能的词是00,01,10,11，一个De Bruijn序列是0011。其中出现00,01,11，10wrapping。此属性自然意味着将 De Bruijn 序列左移(乘以 2 的幂)并取其高位 n 位会导致每个 2 乘数的幂的唯一数字。那么你只需要一个查找表来确定它是哪一个。它的工作原理类似于比二的幂小一的数字，但这种情况下的魔数(Magic Number)不是 De Bruijn 序列，而是一个类似物。定义属性简单地更改为“每个可能的 n 长度单词都显示为长度为 n 的前 m 个子序列的总和，mod 2^n”。此属性是算法工作所需的全部。他们只是使用这种不同类别的魔数(Magic Number)来加速算法。我也是。

构造德布鲁因数的一种可能方法是生成德布鲁因图的哈密顿路径，维基百科提供了此类图的示例。在这种情况下，节点是 2^5=32 位整数，有向边是它们之间的转换，其中转换是左移和根据边的标签 0 或 1 进行二进制或操作。可能有直接模拟 2^n-1 类型的魔数(Magic Number)，可能值得探索，但这不是人们通常构建此类算法的方式。

在实践中，您可能会尝试以不同的方式构建它，尤其是当您希望它以稍微不同的方式运行时。例如，bit twiddling hacks 页面上的前导/尾随零数算法的实现只能返回 [0..31] 中的值。它需要额外检查 0 的情况，它有 32 个零。此检查需要分支，并且在某些 CPU 上可能会太慢。

我这样做的方式是，我使用了一个 64 元素的查找表而不是 32 个元素，生成了随机魔数(Magic Number)，并且为每个元素建立了一个具有两个输入的幂的查找表，检查了它的正确性(单射性)，然后对所有 32 位数字进行了验证。我继续，直到遇到一个正确的魔数(Magic Number)。结果数字不满足“出现所有可能的 n 长度单词”的属性，因为只出现了 33 个数字，这对于所有 33 个可能的输入都是唯一的。

穷举蛮力搜索听起来很慢，特别是如果好的魔数(Magic Number)很少见，但如果我们首先测试两个值的已知幂作为输入，表格很快就会被填满，拒绝很快，拒绝率非常高。我们只需要在每个魔数(Magic Number)之后清空表格。本质上，我利用了一种高拒绝率算法来构造魔数(Magic Number)。

生成的算法是

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 个具有不同魔数(Magic Number)和查找表的输入可能会起作用，这并不是一个很大的想象空间。

在这里，我制作了一个简化版的魔数(Magic Number)生成器代码。如果我们只检查两个输入的幂，它会在 5 分钟内检查所有可能的魔数(Magic Number)，找到 1024 个魔数(Magic Number)。检查其他输入是没有意义的，因为它们无论如何都会减少到 2^n-1 形式。不构建表，但一旦知道魔数(Magic Number)，它就变得微不足道了。

#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();
    }
}