Какой самый быстрый способ вычислить случайного 64-битного соседа с заданным расстоянием Хэмминга, равным 2, и таким же весом в Хэмминге?

Question

Какой самый быстрый способ вычислить случайного 64-битного соседа с заданным расстоянием Хэмминга, равным 2, и таким же весом в Хэмминге?

Независимо от подобных вопросов, на которые уже дан ответ, я хочу знать следующее:

Что самый быстрый способ вычислить случайный 64bit сосед с
дано расстояние Хэмминга 2 а также тот же вес?

Я придумал следующую несколько наивную реализацию. Как я могу сделать (намного) лучше, учитывая, что я использую MSVC на машине с Core i7?

Пример:

Случайный сосед позвонил с

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

0

64bit bit-manipulation c++hamming-distance hammingweight

Решение

Другие решения

Самый быстрый способ, который приходит на ум для «средних» случаев, когда существует множество возможных соседей, заключается в следующем:

приписывать x начальное значение o
Поворот x случайное количество r1
Сброс младшего установленного бита в x
Поворот x случайное количество r2
Установите самый низкий бит сброса в x
Поворот x другой способ r1+r2 мест
Измерьте расстояние Хемминга между x а также o (считать биты в x xor o). Если мы еще не достигли желаемого расстояния, вернитесь к 2.

С положительной стороны, во многих случаях это должно быть довольно быстро. Каждый шаг очень тесно связан с одной инструкцией во вновь добавленной инструкции по обработке битов… и даже без них довольно тривиальные битовые операции (т.е. x = (x | (x+1))). (Между прочим, выполнение этого на процессоре ARM, вероятно, очень близко к одной инструкции на шаг …)

Есть некоторые серьезные недостатки, хотя:

Это будет хорошо работать только для чисел с весом Хэмминга в середине диапазона. Это работает «лучше», когда оригинал имеет вес Хэмминга около 32, и близко к «краям» (скажем, 0-8 установленных битов и 56-64 установленных битов) ему может быть трудно найти подходящего кандидата … и на самых краях он будет пытаться найти кандидата, даже не имея возможности его найти.
Распределение соседей, которое он найдет для некоторого числа, будет сложно искажено. Он будет иметь тенденцию предпочитать «очищать» первый из последовательности единиц и «устанавливать» первый из последовательности нулей.

Если вам нужна одинаковая вероятность получения каждого возможного соседа или вы используете числа с большинством битов, установленных или сброшенных, то есть еще несколько способов, которые приходят на ум, но они вряд ли будут такими же быстрыми, как в среднем ‘ дело.

0

Источник

Accepted Answer

С pdep Вы можете легко «отсчитывать» 0 или 1, пока не окажетесь в позиции, которая была сгенерирована случайным образом. Конечно, ничего не считая.

С помощью 1ull << pos в качестве источника и x (старое число) в качестве маски, _pdep_u64(1ull << unsetPos, x) ставит 1-бит на unsetPos1-й в x,

Так же, _pdep_u64(1ull << setPos, ~x) ставит 1-бит на setPosноль в x,

Просто XOR те, с xочевидно.

0