Поиск всех чисел, которые меньше заданного нет, с меньшим количеством установленных бит, чем заданное нет, но в той же позиции

Question

Как найти все числа, которые меньше заданного нет, и у которых меньше заданных битов, чем заданное нет, но все равно нет. из установленных битов, каждое из сгенерированных значений no будет находиться в положении, аналогичном установленным позициям битов данного no.Приведя один пример, предположим, что данное no равно 13 (1101 в двоичном виде), тогда все сгенерированное no будет 12 (1100 в двоичном виде) ), 9 (1001 в двоичном), 8 (1000 в двоичном), 5 (0101 в двоичном), 4 (0100 в двоичном), 1 (0001 в двоичном). Как видно, это в 1100 (установлены битовые позиции 2 и 3, как в данном № 1101). Я хочу эффективный алгоритм для этого.

Answer 1

Это похоже на перечисление подмножеств набора, определенных битами набора. Здесь ответили: { ссылка }

Answer 2

std::vector<int> subset(int x) {
    std::vector<int> res;
    for(int i = 1; i < x; ++i)
        if (i == (i&x))
            res.push_back(i);
    return res
}

Сложность оптимальна в худшем случае (если x = 2^k-1).