問題概要

非負整数 $N$ が与えられる。次の条件を満たす非負整数 $x$ を昇順にすべて出力せよ。

$x$ と $N$ をともに二進法で表すとき、 $x$ において値が 1 である桁については、 $N$ においても値が 1 である。

制約

$0 \le N \lt 2^{60}$
$N$ を二進法表記したときに、1 の個数は 15 以下

考えたこと

特別な知識なしで解くには、次のようにすればよい。まず、 $N$ を二進法で表したときに、値が 1 であるような桁を $d_{1}, d_{2}, \dots, d_{K}$ としよう。

このとき、ビット全探索を用いて、集合 $\{d_{1}, d_{2}, \dots, d_{K} \}$ の部分集合をすべて列挙して、それを整数値に直して出力すればよい。

しかし、実は部分集合列挙はとても簡単な実装方法が存在する。整数値 $N$ で表される集合の部分集合を列挙するには、次のように書ける。次の for 文により、整数値 S は、N の部分集合を表す。注意点として、この書き方では空集合 ( $S = 0$ のとき) は探索しない。

for (int S = N; S; S = (S - 1) & N) {

}

今回の問題でもこの書き方で AC できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    
    vector<long long> res({0});
    for (long long S = N; S; S = (S - 1) & N) {
        res.push_back(S);
    }
    
    sort(res.begin(), res.end());
    for (auto v : res) cout << v << endl;
}