求出所有小于给定no的数，其集合位数小于给定no但在相同位置上的no

Question

如何找到所有的数字，这些数字小于给定的no，并且这些数字的设置比特数小于给定的no，但无论什么no。举一个例子，假设给定的no是13（二进制中的1101）,那么所有生成的no将是12（二进制中的1100）,9（二进制中的1001）,8（二进制中的1000）,5（二进制中的0101）,4（二进制中的0100）,1（二进制中的0001）。可见，在1100中（设置位位置为2和3，如在给定的1101号中）。我想要一个高效的算法。

Answer 1

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)它的复杂性是最佳的。