0

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;
}
4

2 回答 2

0

The fastest way that comes to mind for 'middle' cases where there are lots of possible neighbours is the following:

  1. Assign x the starting value o
  2. Rotate x a random amount r1
  3. Reset the lowest set bit in x
  4. Rotate x a random amount r2
  5. Set the lowest clear bit in x
  6. Rotate x the other way r1+r2 places
  7. Measure the hamming distance between x and o (count the bits in x xor o). If we've not yet reached the distance we want, go back to 2.

On the positive side, for 'many' cases this should be pretty fast. Every step maps very closely to a single instruction in the newly added bit manipulation instructions... and even without those are fairly trivial bit operations (i.e. x = (x | (x+1))). (Incidentally, doing this on an ARM processor is probably very close to one-instruction per step...)

There are some serious negatives though:

  • This will only work well for numbers with a hamming weight in the middle of the range. It works 'best' when the original has a hamming weight of about 32, and close to the 'edges' (say 0-8 set bits and 56-64 set bits) it may have a hard time finding a valid candidate... and at the very edges it will churn away trying to find a candidate without ever being able to reach it.
  • The distribution of neighbours it will find for some number will be complicatedly skewed. It will have a tendency to prefer 'clearing' the first of a sequence of ones and 'set' the first of a sequence of zeros.

If you need a uniform likelihood of producing each possible neighbour, or are operating with numbers with most bits set or clear, then there are still a few ways that come to mind but they're unlikely to be as fast as this in the 'average' case.

于 2016-07-14T16:12:35.110 回答
0

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.

于 2016-07-14T18:21:56.080 回答