Подмножество связанных битовых манипуляций

Question

Я хочу знать, что означает эта битовая манипуляция:

for (int m = 1; m < (1 << n); ++m) {
    for (int s = m; s; s = (s - 1) & m) {
        // ....
    }
}

Первый цикл for должен перечислять все подмножества n элементов, но что означает второй цикл for

Answer 1

Если s имеет форму ...10000, то s-1 равно ...01111. Затем мы & с m, что оставляет только те 1 в нижней части, которые также присутствовали в m. (Верхние биты s остаются нетронутыми и остаются идентичными битам в m).

Фактически мы удаляем наименьший установленный бит в s и заменяем все младшие биты битами в m,Видно, что это равносильно «обратному отсчету в пределах установленных бит m». То есть, если m имеет k установленных битов, отсчитайте от (1<<k)-1 и для каждого из этих 2 ^k чисел распределите его k биты в позиции k, которые *В 1023 * были установлены биты.

Или, если мы интерпретируем m как набор битов, он перечисляет все подмножества m (включая m, но пропуская пустое подмножество).