подсчитать целые числа, двоичные представления которых отличаются ровно на k позиций от заданного целого числа

Question

Учитывая четыре целых числа a ≤ b ≤ c и k, как вы подсчитываете целые числа в [a, c], двоичные представления которых отличаются ровно на k позиций от позиции b?a, b и c имеют длину около 30 бит.

Answer 1

Если вам нужно вычислить количество для данных a, b и c, а также для всех значений k, то я думаю, что вам лучше всего делать итерации и подсчитывать количество бит в разнице xor.

for (int i = a; i <= c; i++) {
    int d = i ^ b;
    int k = 0;
    while (d != 0) {
        k++;
        d &= (d - 1);
    }
    counts[k]++;
}

Вы даже можете легко распараллелить это.Вам нужно будет сохранить отдельный набор счетчиков для каждого потока и добавить их все в конце, чтобы получить общие итоги.

Для диапазона в 1 миллиард чисел параллельная версия этого алгоритма заняла 3,7секунд на моей машине.

РЕДАКТИРОВАТЬ: На самом деле, есть способ получить счет без перечисления.Вот основная идея для (a, b, c) = (17,25,29) или в двоичном виде (10001,11001,11101).Во-первых, обратите внимание, что диапазон 11000-11011 содержит b, а также полностью содержится в (a, c).Таким образом, эти 2 ^ 2 значения, способствующие выбору (2, k) для каждого счета.Следующий интервал вниз - 10100-10111.Все числа в этом диапазоне имеют как минимум 2 бита, отличных от b, поэтому они вносят выбор (2, k-2) в число k-го числа.Следующий интервал вниз, который полностью содержится в (a, c), равен 10010-10011, что способствует выбору (1, k-1) и так далее.Вы также должны рассчитывать вверх.

2-е редактирование: не удержался от реализации этого.Общее время для 1 миллиарда номеров: 0,004 мс ...

Answer 2

Почему бы просто не перечислить все значения в диапазоне от a до c, проверяя, сколько битов различается для каждого значения? Технический термин для этого в теории информации: Hamming distance http://en.wikipedia.org/wiki/Hamming_distance

Answer 3

Общее число чисел, которые отличаются ровно на k позиций от b и записаны не более чем в 30 битах, составляет binomial(30, k). Это число наибольшее, когда k = 15, и равно binomial(30, 15) = 155117520, так что это лучше, чем перечисление от a до c, но все же может быть много. Однако, если k невелико, то так и есть - просто перечислите все эти числа, которые отличаются ровно k битами, и проверьте, находятся ли они между a и c. Если это слишком медленно, то вы должны сделать это более разумно - например, если a и c имеют одинаковый старший бит, то этот бит должен быть установлен, чтобы вы могли уменьшить возможности.

Answer 4

Запишите двоичное значение для b, переверните k бит и проверьте, нарушает ли оно границы.Для a, b равного 30 битам, не должно быть запретом написание сценария оболочки или программы на C, если разумно k.