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

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

  • Какой самый быстрый способ вычислить случайного 64-битного соседа с заданным расстоянием Хэмминга, равным 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;
}
Источник

2 ответа

Решение

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

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

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

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

Источник

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

  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 установленных битов) ему может быть трудно найти подходящего кандидата... и на самых краях он будет пытаться найти кандидата, даже не имея возможности его найти.
  • Распределение соседей, которое он найдет для некоторого числа, будет сложно искажено. Он будет иметь тенденцию предпочитать "очищать" первый из последовательности единиц и "устанавливать" первый из последовательности нулей.

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

Источник
Другие вопросы по тегам