What is the fastest way to compute a random 64bit neighbor with given hamming-distance of 2 and same hammingweight?

Question

Regardless of similar questions already answered here, I want to know the following:

• What is the fastest way to compute a random 64bit neighbor with given hamming-distance of 2 and same hammingweight?

I have come up with the following somewhat naive implementation. How can I do (much) better, given I am using MSVC on a Core i7 machine?

• Example:

randomNeighbor called with

0000000000000000000000000000000000010111101011110011000111010111

could e.g. result in

0000000000000000000000000000000000010111101011110011001110010111

i.e., hamming-distance is 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

With pdep you can easily "count down" the 0's or 1's until you're in the position that has been randomly generated. Without actually counting anything, of course.

Using 1ull << pos as the source and x (the old number) as mask, _pdep_u64(1ull << unsetPos, x) puts the 1-bit at the unsetPos-th 1 in x.

Similarly, _pdep_u64(1ull << setPos, ~x) puts the 1-bit at the setPos-th zero in x.

Just XOR those with x, obviously.