Генерировать все подмножества множества, заданные двоичным представлением целого числа в C++

Question

В C++ я ищу эффективный алгоритм для генерации всех целых чисел, так что их двоичное представление является подмножеством набора, который задается двоичным представлением целого числа N. Под эффективным я имею в виду, что я не хочу проходить цикл все целые числа меньше N, чтобы проверить, являются ли они подмножествами, главным образом потому, что N может быть очень большим.

У меня была идея сгенерировать все возможные подмножества целого числа, соответствующего весу Хэмминга N, и затем переместить их в правильные позиции с помощью <<, но я пока не могу найти хороший способ сделать это.

Пример:

Для набора 110100, заданного целым числом N=52, все возможные подмножества будут:

{} 000100,010000,010100,100000,100100,110000

соответствует целым числам {4,16,20,32,36,48}, что я и хочу сгенерировать.

Answer 1

Пусть P будет popcount(N), количество битов, которые установлены. Число результатов тогда 2^P - 2.

Обрабатывать N как логический массив (биты). Для каждого установленного бита сгенерируйте два подмножества: одно с установленным этим битом и одно без него. Это можно сделать рекурсивно, пока не будут установлены биты.

Наконец, отбросьте исходный N из результатов, а также 0 (согласно вашему примеру).

Временная сложность линейна по размеру выхода, то есть O (2^P).