Какова логика бинарного сравнения между элементами и количеством элементов при поиске подмножества?

Question

Рассмотрим следующую проблему из книги (https://cses.fi/book/book.pdf): "Сначала рассмотрим задачу генерации всех подмножеств набора из n элементов. Например, подмножествами {0,1,2} являются φ,{0}, {1}, {2}, {0,1}, {0,2}, {1,2} и {0,1,2}. Существует два распространенных метода генерации подмножеств: мы можемвыполнить рекурсивный поиск или использовать битовое представление целых чисел. "

Решение № 2 в книге (стр. 48, PDF, стр. 58) следующее:

for (int b = 0; b < (1<<n); b++) {
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        if (b&(1<<i)) subset.push_back(i);
    }
}

Мой вопрос:почему работает сравнение (b&(1<<i))? Что это делает в фоновом режиме? Я пробовал это вручную для подмножеств {0, 1}, и это работает безупречно, но только почему сравнения между ними работают?b является счетчиком количества элементов, а (1<<i), насколько я понимаю, в основном эквивалентно 2 ⁱ . Почему все это работает? Это похоже на магию.

PS. Я знаю, что книга - плохой справочник по C ++, я читаю ее больше для объяснений алгоритма.

Answer 1

Думайте о целых как о битовых строках, а не числовых значениях

Здесь каждый бит в b представляет, находится ли соответствующий элемент в подмножестве или нет.Цикл от 0 до 2 ⁿ повторяет все возможные состояния n битов, поскольку каждое состояние является целым числом от 0 до 2 ⁿ .Следовательно, значения b будут представлять все возможные подмножества.

Чтобы преобразовать значение b в соответствующее подмножество, мы зациклим каждый из элементов и проверим, находится ли элемент вподмножество.Мы добавляем элемент в вектор, если соответствующий бит установлен в b.Чтобы проверить, установлен ли i-й бит в b, мы вычисляем b & (1 << i).

& - битовое И, поэтому бит в результате будет установлен, только если этот бит установленв обоих операндах.1 << i - битовая маска с установленным i битом, а все остальные биты не установлены.Когда мы вычисляем побитовое И для b и 1 << i, все биты, кроме i -ых, не будут установлены, потому что соответствующий бит не установлен в битовой маске.i -й бит будет установлен, только если установлен i-й бит в b.Таким образом, мы получим что-то отличное от 0, если установлен i -й бит, и 0 в противном случае.Поскольку преобразование из int в bool тестирует, если значение не равно 0, тело оператора if будет выполняться, если установлен i -й бит b.

Answer 2

Назначьте каждому элементу в наборе различную степень двойки (1, 2, 4, 8 и т. Д.) В качестве идентификатора. Каждое подмножество является комбинацией различных элементов в наборе, которые могут быть представлены комбинациями идентификаторов. Добавление идентификаторов в подмножестве даст уникальный номер.

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

1 << i соответствует одному из этих идентификаторов, b & (1 << i) проверит текущее подмножество, чтобы определить, принадлежит ли ему элемент i.

Answer 3

В качестве двоичных строк используется целое число.nth-bit = 1 означает, что n-й элемент присутствует в этом подмножестве.Аналогично, значение 0 означает, что его нет в подмножестве.& (1<<i) используется для проверки, равен ли i-й бит единице (или, другими словами, если установлен i-й бит)