Представьте 10000 логических значений, используя только 10000 бит

Как объясняет Википедия, битовое поле здесь является подходящим выбором. битовое поле, которое может содержать 10 000 бит, имеет 2 ^ 10 000 состояний.

Хорошим выбором для этого (учитывая, что целые числа являются 32/64-битными) является битовый вектор, о котором спрашивают и подробно объясняют здесь:

бит-векторная реализация набора в Programming Pearls, 2nd Edition

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

Вы можете заставить bool принимать 1 бит, например, если у вас их куча, например. в структуре, например:

struct A { bool a:1, b:1, c:1, d:1, e:1; };

Вышеупомянутый метод не будет полезен, если количество переменных велико. Поэтому вместо этого создайте массив целых чисел размером 10000/4*8. Он создаст ровно 10000 бит. Теперь вы можете получить доступ к каждому биту, используя смещение и ‹‹ или >> (например, для доступа к 55-му биту используйте пол (55/4 * 8) и >> 55%32. вы можете получить этот бит).

В C++ это можно сделать очень просто, используя один из двух контейнеров стандартной библиотеки:

std::vector<bool>

Эта специализация стандартного вектора действует (почти) как любой другой вектор, но сжимает его содержимое до одного бита на элемент. Помимо удовольствия от этого факта, вы можете просто обращаться с ним как с вектором:

// Create a vector of 10000 booleans
std::vector<bool> lots_of_bits(10000);
// Set all the odd ones to true
for (int i = 1; i < lots_of_bits.size(); i += 2) {
  lots_of_bits[i] = true;
}
// Add another 100 trues at the end
for (int j = 0; j < 100; ++j) {
  lots_of_bits.push_back(true);
}
// etc.

std::bitset<N>

«Новый, улучшенный» битовый вектор, который не претендует на роль стандартного контейнера. В частности, он имеет фиксированный размер, и вам нужно знать размер во время компиляции. Это может быть немного ограничительным, но в остальном это довольно полезный класс. Как и std::vector<bool>, он реализует оператор [] для получения и установки отдельных битов. Он также поддерживает побитовые логические операторы &, |, '^' и ~ (и, или, xor и нет), а также битовые сдвиги влево и вправо и некоторые другие утилиты.

Вас беспокоит, что для доступа к битовому номеру n требуется сдвиг n раз? Если это так, вы можете решить проблему, разделив свои 10 000 битов на 10 000 / 8 сегментов, используя массив символов (предполагая, что здесь C или C++). Теперь вы можете получить доступ к биту номер n, выяснив, в какой корзине находится этот бит (n / 8), а затем в какой позиции внутри корзины (n % 8). Затем вы просто делаете маскировку. Не требуется дополнительное хранилище (кроме заполнения в конце, поэтому несколько дополнительных битов, если у вас нет идеального кратного 32 бита).