Привет, мир! Вы, должно быть, столкнулись с вопросом в программировании, где вы должны сгенерировать все подмножества данного набора и выполнить некоторые операции с этими подмножествами, и что мы обычно делаем, это используем рекурсию для генерации всех подмножеств, НО есть также другой способ выполнить это задача итеративно, и это тоже без использования каких-либо дополнительных функций, что означает отсутствие накладных расходов на вызов функции.
Здесь мы говорим о BitMasking. Прежде всего, мы должны помнить, что целое число - это просто набор битов, связанных друг с другом. В Bitmasking идея состоит в том, чтобы визуализировать число в форме его двоичного представления. Некоторые биты «установлены», а некоторые «не установлены», «установлен» означает, что его значение равно 1, а «не установлено» означает, что его значение равно 0.
Битовая маска - это просто двоичное число, которое что-то представляет.
Предположим, что «n» - это количество элементов в нашем наборе. Затем, Если мы запишем двоичное представление всех чисел от 0 до (2 ^ n) -1, мы получим все возможные комбинации выбора n элементов. Возьмем пример:
suppose the set we have is {1 2 3} and we want to get all the possible combinations of selecting the given 3 items of the set. Then (2^3)-1 is 7 , so we write all the numbers from 0 to 7 and binary representation of those numbers will give us the possible combinations of selecting the 3 items.{1 2 3} Number Binary Representation Subset 0 0 0 0 { } 1 0 0 1 { 3} 2 0 1 0 { 2 } 3 0 1 1 { 2 3} 4 1 0 0 {1 } 5 1 0 1 {1 3} 6 1 1 0 {1 2 }7 1 1 1 {1 2 3} In this way, we have actually generated all of our subsets😎
«Маска» означает скрытие чего-либо. Двоичные представления 1,2,3,…., 7 на самом деле представляют маску. В конкретном подмножестве i-й элемент набора принадлежит к нему тогда и только тогда, когда установлен i-й бит маски (значение 1).
Как показано в приведенном выше примере: если бит установлен (значение 1), то мы возьмите соответствующий элемент из нашего массива в нашем подмножестве. Например, в двоичном представлении 1, то есть 001, установлен 3-й бит, поэтому мы берем 3-й элемент в нашем подмножестве и игнорируем 1-й и 2-й элементы. Для 6 двоичное представление - 110, поэтому мы берем 1-й и 2-й элементы в нашем подмножестве и игнорируем 3-й элемент.
Примечание. Фактически, первый бит всегда будет младшим значащим битом и всегда будет отображаться справа, это означает, что в 001 установлен 1-й бит, поэтому он фактически представляет {1} , в 110 устанавливаются 2-й и 3-й бит, представляющие {2, 3}. Мы взяли представление в приведенном выше примере просто для лучшего понимания, потому что, когда мы его реализуем, этот порядок на самом деле не имеет значения, поэтому мы можем безопасно визуализировать его так, как показано в приведенном выше примере.
Мы можем выполнять следующие полезные операции с битовыми масками:
Пусть 'B' представляет битовую маску
1) Установите i-й бит. : B = B | (1 ‹---------------- i)
2) Сбросить i-й бит: B = B &! (1 ‹---------------- i)
3) Проверьте, установлен ли i-й бит: B & (1 ‹---------------- i) → если i- -й бит установлен, мы получим ненулевое целое число, иначе мы получим ноль
4) Переключите i-й элемент набора: B = B ^ (1 ‹---------------- i)
5) Включите все биты в наборе размера n: B = (1 ‹* n) -1
Теперь еще одна важная вещь, которую следует отметить, это то, что общее количество возможных подмножеств равно 2 ^ n, поэтому для итерации по всем подмножествам набора размером 'n' мы должны запустить цикл 2 ^ n раз и 2 ^ n = (1 ‹* n), поэтому мы просто запускаем цикл (1 ‹* n) раз.
Реализация:
достаточно теории, давайте посмотрим на реализацию
Алгоритм:
1. Выполните цикл для "маски" для всех чисел от 0 до (2 ^ n) -1.
2. Когда внутри этого цикла запустите цикл для 'i' от 0 до n-1.
3. Внутри этого цикла проверьте, установлен ли i-й бит (значение 1).
4. Если Установлен i-й бит, затем мы включаем этот элемент в наше подмножество, иначе нет.
5. Готово.
Примечание по реализации:
Итак, мы увидели, что битовая маска - это очень полезный метод, но мы должны использовать его осторожно:
1) Решения, использующие битовую маску, обычно занимают экспоненциальное время.
Временная сложность приведенного выше кода составляет O ((2 ^ n) * n), поэтому используйте его только для небольших ограничений (обычно для n≤20 ).
2) Проверьте размер набора, чтобы решить, использовать ли 'int' или 'long long int', если размер набора больше 20, то рекомендуется не использовать Bitmasking вообще
3) Используйте круглые скобки при работе с побитовыми операторами.
На сегодня все. Какие-либо предложения? Дай мне знать в комментариях!
А пока Tschüß!
