在给定的汉明距离为2和相同的蜂巢重量的情况下，计算64位随机邻居的最快方法是什么？

Question

尽管这里已经回答了类似的问题，但我想知道以下几点：

• 在给定的汉明距离为2和相同的蜂巢重量的情况下，计算随机64位邻居的最快方法是什么？

我想出了以下一些幼稚的实现。如果我在核心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

使用pdep，您可以轻松地“数”0或1，直到您处于随机生成的位置。当然也不算任何事。

使用1ull << pos作为源，使用x (旧数字)作为掩码，_pdep_u64(1ull << unsetPos, x)将1位放在x中的unsetPos-th 1上。

类似地，_pdep_u64(1ull << setPos, ~x)将1位放在x中的setPos-th 0.

很明显，只有那些带有x的。

Answer 2

在有许多可能的邻居的“中间”情况下，最快的方法是：

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

从积极的方面来看，对于“很多”案例来说，这应该是相当快的。每个步骤都非常接近于新添加的位操作指令中的单个指令.即使没有这些操作，也是相当琐碎的位操作(即x = (x | (x+1)))。(顺便说一句，在ARM处理器上这样做可能非常接近于每步一条指令.)

不过，也有一些严重的负面影响：

• 这只会很好地工作的数字与汉明重量在中间的范围内。它的工作“最好”时，原有一个汉明重量约32，并接近‘边缘’(例如0-8集位和56-64集位)，它可能有一个困难的时间找到一个有效的候选.而在最边缘，它将努力寻找一个候选人，而从来没有能够达到它。
• 它将找到的一些邻国的分布将是复杂的倾斜。它会倾向于“清除”第一个1序列和‘设置’一个零位序列的第一个。

如果你需要一个统一的可能性来产生每一个可能的邻居，或者是用大多数位数设定或清除的数字操作，那么仍然有几种方式出现在脑海中，但在“平均”情况下，它们不太可能像这个速度一样快。