Использование N-битного целого числа для представления N логических значений является частным случаем структуры данных, известной как совершенная хеш-таблица . Обратите внимание, что вы явно используете dicts (которые являются общими хеш-таблицами) в идее, которая побудила вас задуматься о наборах битов. Это хеш-таблица, потому что вы используете хеш-коды для нахождения значения, и она идеальна, потому что у вас никогда не бывает коллизий. Особый случай связан с тем, как таблица упаковывается и хранится.
Сформулируйте хеш-функцию, которая показывает, чем она отличается от массива:
int bitset_hash(int n) {
// domain of this function is only non-negative ints
return 1 << n;
}
Обратите внимание, что bitset_hash (3) имеет значение 0b1000, что соответствует 4-му элементу (смещение / индекс 3) при использовании C int и побитовых операций. (Из-за деталей реализации хранилища побитовые операции также используются для манипулирования конкретным элементом из хеша.)
Расширение подхода к использованию побитового и / -or / -xor для операций над множествами распространено и не требует какого-либо специального имени, кроме "операций над множествами" или, если вам нужно модное слово , "теория множеств".
Наконец, вот еще один пример его использования в простом сите (я использовал этот код в решениях Project Euler):
class Sieve(object):
def __init__(self, stop):
self.stop = stop
self.data = [0] * (stop // 32 // 2 + 1)
self.len = 1 if stop >= 2 else 0
for n in xrange(3, stop, 2):
if self[n]:
self.len += 1
for n2 in xrange(n * 3, stop, n * 2):
self[n2] = False
def __getitem__(self, idx):
assert idx >= 2
if idx % 2 == 0:
return idx == 2
int_n, bit_n = divmod(idx // 2, 32)
return not bool(self.data[int_n] & (1 << bit_n))
def __setitem__(self, idx, value):
assert idx >= 2 and idx % 2 != 0
assert value is False
int_n, bit_n = divmod(idx // 2, 32)
self.data[int_n] |= (1 << bit_n)
def __len__(self):
return self.len
def __iter__(self):
yield 2
for n in xrange(3, self.stop, 2):
if self[n]:
yield n