2026-09-29
submasks.rs
fn submasks(mask: u32) -> Vec<u32> {
}
ビット集合 mask の部分集合をすべて、大きい順に並べて返す submasks を書いてください。部分集合とは、mask で1になっているビットのうち、いくつかだけを1にした値です。mask 自身と 0 も含めます。mask が 0 なら [0] を返します。
入力例 1
submasks(0b1010)
出力例 1
[10, 8, 2, 0]
入力例 2
submasks(5)
出力例 2
[5, 4, 1, 0]
入力例 3
submasks(0)
出力例 3
[0]
Reference
fn submasks(mask: u32) -> Vec<u32> {
std::iter::successors(Some(mask), |&sub| (sub != 0).then(|| (sub - 1) & mask)).collect()
}
sub の次に小さい部分集合は (sub - 1) & mask で求まります。sub - 1 は sub の最下位の1を0にし、それより下の0をすべて1にします。そこから mask にあるビットだけを残すと、sub の最下位の1を外し、その下にある mask のビットをすべて立てた値になります。これは sub より小さい部分集合のうちで最大のものなので、mask から始めて繰り返せば、すべての部分集合が1回ずつ大きい順に出てきます。sub が mask 自身である最初の1回は mask & (mask - 1) で、最下位の1ビットを消す式そのものです。
止める条件を while sub != 0 にすると、最後の 0 が抜けます。かといって 0 を入れたあとも次を計算すると、0 - 1 を求めることになります。u32 の引き算はデバッグビルドではここで panic し、リリースビルドでは u32::MAX に回り込みます。u32::MAX & mask は mask なので、列挙が最初からやり直しになって終わりません。0 を返したら、引き算をせずにそこで止める必要があります。
参考実装の std::iter::successors は、今の値から次の値を作り、None が返ったところで止まります。(sub != 0).then(|| …) のクロージャは条件が真のときしか呼ばれないので、sub が 0 のときは sub - 1 を計算しません。見た目の似た then_some((sub - 1) & mask) では、引数が呼び出しの前に評価されるため 0 - 1 が計算され、デバッグビルドでは panic します。
掲載したのは参考実装で、唯一の正解ではありません。loop の中で sub を Vec に積み、sub == 0 なら返す書き方でも同じ結果になります。(0..=mask).rev().filter(|s| s & !mask == 0) も正しい部分集合を返しますが、mask の値に比例する回数だけ回るので、上位のビットが立った mask では、部分集合が数個しかなくても膨大な時間がかかります。