Как работает итерация подмножеств подмножеств?

Question

Я читаю
for ( x = y; x > 0; x = ( y & (x-1) ) )

генерирует все подмножества битовой маски y.

Как работает эта итерация? Любое интуитивное объяснение?

источник: http://codeforces.com/blog/entry/45223

см. раздел неоптимального решения.

Answer 1

Интуиция: взятый как число, битовая маска y не может иметь больше чем y подмножества. Итак, отсчитывая xвы гарантированно попадете в каждое подмножество y с помощью маскировки. Но это создает много дубликатов. Подумать о 1101, Если вы отсчитываете от этого и маскируете yпоследовательность пойдет. 1101, 1100, 1001, 1000, 1001, 1000, и так далее. Назначая x В результате операции маскирования вы переходите к ее последнему появлению.

Доказательство: это приводит к простому доказательству по индукции. Очевидно, что для битовых строк длиной 1 эта процедура работает. Только два подмножества, 1, а также 0, испускаются в этом порядке.

Теперь предположим, что эта процедура работает для цепочек битов длины N, предполагать Z кусочек длины N, Если вы создаете цепочку битов 0Zзатем вы следуете той же последовательности, что и для Z наряду с тем, что вычитание никогда не включает биты более высокого порядка. Если вы создаете цепочку битов 1Zтогда происходит следующее: для первого 2^nnz(Z) шаги, оригинал Z последовательность следует, с 1 предваряется. И для последнего 2^nnz(Z) шаги, оригинал Z последовательность следует, с 0 предваряется. Поскольку процедура посещает каждый элемент меньшей последовательности дважды, предваряя 1 в первый раз, и 0 во-вторых, мы заключаем, что процедура излучает каждое подмножество 1Z,

Взятые вместе, мы видим, что процедура работает для всех битовых строк.

Answer 2

Первый простой факт, который используется здесь, заключается в том, что если мы, скажем, принять значение 7 (111 в двоичном коде) и начать уменьшать его многократно (вплоть до 0) мы пройдем через двоичные представления

111, 110, 101, 100, 011, 010, 001, 000

который довольно очевидным образом представляет все возможные подмножества исходного 3-множества.

Вторым фактом является то, что в двоичном "для уменьшения x" (" вычесть 1 из x") означает: инвертировать все биты x начиная с наименее значимого (крайнего справа) и слева до (и включая) первого 1 в представлении x, "Влево" здесь означает "в направлении увеличения битовой значимости".

Например

00001000 - 1 = 00000111, i.e. we invert the `1000` tail
01010101 - 1 = 01010100, i.e. we invert just the `1` tail
10000000 - 1 = 01111111, i.e. we invert the whole thing
and so on

Операция декремента "выключает" наименее значимый 1 бит в двоичном представлении и "включает" все нулевые биты справа от него.

Теперь, третий факт, что в вашем случае 1 биты x всегда подмножество 1 биты y, так как мы начинаем с x = y и делать x = (whatever) & y на каждой итерации.

Когда мы делаем x - 1 мы "выключаем" 0) нижайший 1 в x и "включить" (установите на 1) все 0 в x справа от этого самого низкого 1,

Когда мы следуем этому с & y в x = (x - 1) & y мы "выключаем" какой-то оригинальный бит y в x и "включить" все нижние оригинальные биты y в x,

На этом этапе уже должно быть достаточно очевидно, что эта операция является просто "маскированным декрементом" x: при выполнении x = (x - 1) & y мы просто уменьшаем значение x при условии, что только биты маскируются y сформировать значение xв то время как все остальные биты являются просто незначительными "битами заполнения".

Провести параллель к приведенному выше примеру с уменьшением 7, начальная стоимость y может выглядеть как 10010100, операция x = (x - 1) & y увидим это значение как "распределенную семерку" (неформально). x будет проходить через следующие значения

1..1.1.., 1..1.0.., 1..0.1.., 1..0.0.., 0..1.1.., 0..1.0.., 0..0.1.., 0..0.0..

где . обозначает "битовые" биты " x, которые на самом деле не участвуют в этой операции "маскированного декремента" (в действительности они будут 0). Обратите внимание на сходство с исходным примером с 7,