Двоичные соседи десятичного числа

Question

Предположим, у меня есть десятичные числа от 0 до 2^L. Каждое из этих десятичных чисел может быть представлено в виде двоичного числа длиной L. Теперь меня интересует функция, которая принимает одно десятичное число, а затем вычисляет все L десятичные числа, для которых двоичное представление отличается только в одной позиции. Меня интересует самое быстрое решение этой проблемы. Пример:

L=3--> Numbers between 0 and 7 F(2) = (0,3,6) since 2= 010 -> 0=000, 3=011, 6=110

Надеюсь, у вас есть идея и спасибо заранее :)

Answer 1

Вы можете использовать бит-сдвиги для этого:

def neighbors(n, bitLength):
    return map(lambda b: n ^ (1 << b), range(bitLength))

>>> print(list(neighbors(2, 3)))
[3, 0, 6]

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

Answer 2

Чистая реализация на python с использованием оператора xor ^

def neighbors(n, bits):
    for bit in range(bits):
        yield n ^ (2 ** bit)

Это работает с вашими примерами чисел.

>>> list(neighbors(2, 3))
[3, 0, 6]

Вот простое решение, которое создает внешний продукт из последовательности чисел.

import numpy as np

def array_neighbors(numbers, bits=8):
    flip_bits = 2 ** np.arange(bits)
    return np.bitwise_xor.outer(numbers, flip_bits)

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

>>> array_neighbors([0,1,2,3,4,5,6,7], 3)
[[1 2 4]
 [0 3 5]
 [3 0 6]
 [2 1 7]
 [5 6 0]
 [4 7 1]
 [7 4 2]
 [6 5 3]]

Это довольно быстро и может обработать большой массив целых чисел за несколько миллисекунд.

>>> a_million_numbers = np.random.randint(0, 256, 1_000_000)
>>> %timeit array_neighbors(a_million_numbers)
67.8 ms ± 3.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)