计算给定汉明距离 2 和相同汉明权重的随机 64 位邻居的最快方法是什么？

Question

不管这里已经回答了类似的问题，我想知道以下内容：

• 计算 随机 64 位 邻居 的最快方法是什么 给定 汉明距离 2 和 相同的汉明重量?

我想出了以下有点天真的实现。如果我在 Core i7 机器上使用 MSVC，我怎样才能做得更好？

• 示例：

randomNeighbor 调用

0000000000000000000000000000000000010111101011110011000111010111

可以例如结果

0000000000000000000000000000000000010111101011110011001110010111

即汉明距离为 2。

int msb = 36;  // msb
int hw = 19;   // hammingweight

long long randomNeighbor(long long number) {
    long long neighbor = number;

    int setBitCnt = 0;
    int unsetBitCnt = 0;

    int setBitNr = rnd(hw - 1);
    int unsetBitNr = rnd(msb - hw - 1);

    bool setBit = true;
    bool unsetBit = true;

    for (int x = 0; setBit && unsetBit && x < msb; x++)
    {
        if (_bittest64(&neighbor, x))
        {
            if (setBitCnt == setBitNr)
            {
                _bittestandreset64(&neighbor, x);
            }
            setBitCnt++;
        }
        else
        {
            if (unsetBitCnt == unsetBitNr)
            {
                _bittestandset64(&neighbor, x);
            }
            unsetBitCnt++;
        }
    }
    return neighbor;
}

Answer 1

对于有很多可能邻居的 'middle' 情况，想到的最快方法如下：

1. 分配x起始值o
2. 旋转x一个随机数r1
3. 重置 x
中的最低设置位
4. 旋转x一个随机数r2
5. 设置x中的最低清除位
6. 向另一方向旋转 x r1+r2 个位置
7. 测量x和o之间的汉明距离（计算x xor o中的位数）。如果我们还没有达到我们想要的距离，回到2。

从积极的方面来说，对于 'many' 个案例，这应该是相当快的。每个步骤都非常紧密地映射到新添加的 bit manipulation instructions 中的单个指令......即使没有这些也是相当微不足道的位操作（即 x = (x | (x+1))）。 （顺便说一句，在 ARM 处理器上执行此操作可能非常接近每步一条指令...）

虽然有一些严重的负面影响：

• 这仅适用于汉明权重在范围中间的数字。当原始汉明权重约为 32 且接近 'edges'（比如 0-8 设置位和 56-64 设置位）时，它可以工作 'best' 它可能很难找到有效的候选人...在最边缘，它会流失，试图找到一个候选人，但永远无法找到它。
• 它会为某些数字找到的邻居分布会出现复杂的倾斜。它将倾向于选择 'clearing' 1 序列中的第一个，'set' 0 序列中的第一个。

如果您需要产生每个可能的邻居的统一可能性，或者使用大多数位设置或清除的数字进行运算，那么仍然可以想到一些方法，但它们不太可能像这在 'average' 案例中。

Answer 2

使用 pdep，您可以轻松地 "count down" 0 或 1，直到您处于随机生成的位置。当然，实际上没有计算任何东西。

使用 1ull << pos 作为源和 x（旧数字）作为掩码，_pdep_u64(1ull << unsetPos, x) 将 1 位放在 unsetPos-th 1 in x.

类似地，_pdep_u64(1ull << setPos, ~x) 将 1 位放在 x 中的第 setPos 个零处。

很明显，只需对 x 进行 XOR。