マスク付きbit全探索

bit全探索するときに

特定のbitの状態を固定したいときってありませんか？私はありました

ちょうどこんな感じの挙動がほしいときです
3,5ビット目は常に0
000'000 → 000'001 → 000'010 → 000'011 → 001'000 → 001'001 → 001'010 → 001'011 →
100'000 → 100'001 → 100'010 → 100'011 → 101'000 → 101'001 → 101'010 → 101'011

愚直な実装

std::uint64_t mask = 0b101011;

for (std::uint64_t i = 0; i < (std::uint64_t{1} << 6); ++i) {
    if (i & ~mask) continue;

    .....
}

コレだと結局2^6の全てのパターンを走査していて、本来2^4回のループで済むところを（処理が飛ばされはするものの）2^6-2^4回だけ無駄にループしている。

固定されるビットの数が1つのときにループの半分が無駄になり、以降固定されるビットの数が増えるたびに無駄が増えるので、大半の状況ではループの殆どが無駄になる

これを2^4回のループで済ませられるようにしたい

方針

立っているビットの位置を調べて...とかやってると日が暮れそうなので少ない手数（可能なら1行で）できる方法を考える

とりあえず細かく分けて考える

• 000'000 → 000'001 → 000'010 → 000'011 の遷移
• 001'000 → 001'001 → 001'010 → 001'011 の遷移
  • 普通に+1すれば良い
• 000'011 → 001'000 の遷移
  • 3ビット目に1があると思って+1するとうまく行く
  • 000'111 → 001'000
• 001'011 → 100'000 の遷移
  • 3ビット目と5ビット目に1があると思って+1するとうまく行く
  • 0 11'111 → 10'000

というわけで

1. 固定されているビットを全部立てる
2. +1する
3. 固定されているビットを全部下ろす

とすればよい
（つまりインクリメントのときだけ繰り上がり用にビットを立てておく、という作戦）

コードにするとこんな感じ

std::uint64_t mask = 0b101011;
for (...;...; i = ((i | ~mask) + 1) & mask) {

しかしこれだと101'011 → 000'000 と遷移してしまうので、元の終了条件だと無限ループしてしまう
動作確認用

状況的には （そんなことをやる機会はまずないだろうけど）64bit変数で2^64パターンの愚直なbit全探索ができないのと似ているので泥臭い方法で対処する

こんな感じのループはできない

for (std::uint64_t i = 0; i < (std::uint64_t{1} << 64); ++i) {
for (std::uint64_t i = 0; i != (std::uint64_t{1} << 64); ++i) {

仕方ないのでこうする()

std::uint64_t mask = 0b101011;
std::uint64_t lim = std::uint64_t{1} << 6;
for (...; i < lim; i = (i != mask ? ((i | ~mask) + 1) & mask : lim)) {

動作確認用

ここまで来ると専用のrangeを作ったほうが良さそう

逆順

逆順にたどること自体は簡単で

i = (i - 1) & mask;

とすると繰り下がりで発生した余分なビットを消せるので逆順に走査できる

ただし、終了条件が非常に面倒なのでこれまた専用のrangeを作るか、昇順の方法を流用して

std::uint64_t mask = 0b101011;
std::uint64_t lim = std::uint64_t{1} << 6;
for (...; i < lim; i = (i != mask ? ((i | ~mask) + 1) & mask : lim)) {
    auto j = ~i & mask;

とかが良さそう
動作確認用

固定するビットを0じゃなくて1にしたりしたい

適当にmaskすればいいんじゃないかな

std::uint64_t mask = 0b101011;
std::uint64_t patt = 0b010000; // 5ビット目は1
std::uint64_t lim = std::uint64_t{1} << 6;
for (...; i < lim; i = (i != mask ? ((i | ~mask) + 1) & mask : lim)) {
    auto j = i | patt;

どうでもいい一言

なんでstd::bitsetさん.to_int<std::uint16_t>()みたいなビット幅を選べる整数への変換インターフェースが無いんですか！ ullongってなんだよ！環境依存じゃねーか!