Техника битовых манипуляций для замены логических массивов фиксированного размера менее 64

Опубликовано: 20 Сентября, 2022

Сложность пространства — наиболее недооцениваемый актив программистами. При отправке решения едва можно увидеть превышение лимита памяти (MLE). Но экономия памяти — это самое важное, о чем должен заботиться программист. Если нужно создать приложение для пользователя, оно должно быть максимально эффективным с точки зрения использования памяти.
Логические массивы использовались в качестве контейнера для решения различных задач. В этой статье основное внимание уделяется обсуждению альтернатив логическим массивам.

Целочисленная переменная как контейнер

Как правило, переменная Integer имеет 4 байта (с учетом C++), в результате чего для представления числа требуется 32 логических бита. Например, чтобы представить 10, логические биты могут быть записаны как:

int a = 10

In Memory-
00000000000000000000000000001010 (Binary of 10 in 32-bit integer)

Это означает, что эти биты можно использовать как логическое значение внутри логического массива размером 32. При необходимости можно использовать 64-битное целое число для увеличения размера.

Как использовать целочисленную переменную в качестве контейнера?

Давайте подробно обсудим, как использовать переменную Integer в качестве контейнера.

Первый шаг — инициализировать целочисленную переменную как 0, чтобы получить логический контейнер размера 32 со всеми битами, первоначально ложными.

Установите бит в true:
Установите для любого бита значение true для любого желаемого местоположения с помощью побитовых операторов, таких как операторы AND, NOT, OR и SHIFT. Например, чтобы установить бит в истину в позиции 7-

Use shift and bitwise OR operator to make the ith bit to 1 (true)
int a = 0;
a |= (1 << 7);
Here a will become : 00000000000000000000000010000000
                                                                                              ↑
                                                                                              0th bit

Шаг 1: Сначала переместите 1, который равен (..0001) в двоичном формате, на 7 шагов осталось, чтобы сделать его равным (..10000000).
Шаг 2: Далее сделайте побитовое или с числом.
Шаг 3: Поскольку 1 ИЛИ 0 = 1 и 1 ИЛИ 1 = 1, это установит 7 -й бит в единицу, не затрагивая другие биты.

Установите бит в false:

Например, чтобы сбросить бит в false в позиции 7

Use shift and bitwise NOT and AND operator to make the ith bit to 0(false).
int a = 0;
a |= (1 << 7); // To set 7th bit
a &= ~(1 << 7); // To reset 7th bit

Шаг 1: Сначала переместите нашу 1, которая является (..0001) в двоичном формате, на 7 шагов до конца, чтобы сделать ее как (..10000000).
Шаг 2: Инвертируйте биты, чтобы они выглядели как (…1101111111).
Шаг 3: Выполните операцию И с числом.
Шаг 4: Поскольку 1 И 0 = 0, 0 И 0 = 0, 1 И 1 = 1, это установит 7 -й бит в единицу, не затрагивая другие биты.

Получить значение i -го бита:

Например, чтобы получить значение 7 -го бита-

Use AND operator to print.
int a = 0;
a |= (1<<7); // To set 7th bit
Print((a>>7)&1);  // this will print 1(True)
a &= ~(1<<7); // To reset 7th bit
Print((a>>7)&1); // this will print 0(false)

Ниже приведена реализация вышеуказанного подхода:

Решите строки панграммы:

Давайте решим проблему строк панграммы, используя описанный выше подход.

Подход:

Известно, что английские алфавиты нижнего регистра в диапазоне от (az) имеют количество не более 26. Таким образом, в этом подходе можно использовать логический массив постоянного размера. Это позволит оптимизировать пространственную сложность кода.

Ниже приведена реализация строк панграммы с использованием логического массива:


РЕКОМЕНДУЕМЫЕ СТАТЬИ