2026-11-07
shrink.rs
fn holds(x: u32) -> bool {
x.count_ones() < 3
}
fn main() {
let mut x: u32 = 0xDEAD_BEEF;
loop {
let smaller = [x & (x - 1), x >> 1];
match smaller.into_iter().find(|&c| !holds(c)) {
Some(c) => x = c,
None => break,
}
}
println!("{x}");
}
これは何を出力するでしょうか?
Answer
Output
13
holds は「立っているビットが3個未満」という性質で、0xDEAD_BEEF はその反例です。ループは、反例をより小さな候補に置き換えられる限り置き換えます。プロパティベーステストが見つけた反例を読みやすい大きさまで縮める手順で、候補に置き換えるのは、候補にもビットが3個以上立っていて反例のままのときだけです。0xDEAD_BEEF には24個のビットが立っているので、1回ずつ追うと何十回も回ります。追う代わりに、ループが止まるときの x の形と、それまでに変わらないものを考えます。
1つ目の候補 x & (x - 1) は、x の一番下の1だけを0にした値です。x - 1 は一番下の1とそれより下の0をすべて反転させるので、& を取るとその1だけが消えます。立っているビットが1個減るので、この候補が反例なのは x に4個以上立っているときです。2つ目の候補 x >> 1 は全体を1ビット右へずらし、最下位ビットが1ならそれを落とします。find は配列の先頭から調べるので、4個以上立っている間は必ず1つ目が選ばれ、上の3個を残して下のビットが1つずつ消えます。ちょうど3個になると1つ目は反例でなくなり、2つ目は最下位ビットが0の間だけ反例のまま使えます。止まるのは、立っているビットが3個で、最下位ビットが1のときです。
どちらの候補も、上の3個のビットの並び方を変えません。0xDEAD_BEEF の先頭の16進数 D は2進数で 1101 なので、上の3個はビット31、30、28で、その並びを最下位までずらした 1101 が最後の x です。10進数で 13 になります。
「反例を縮めるのだから、立っているビットが3個の最小の数 7 に着く」と考えると間違えます。縮小は、その時点の反例から一歩で行ける候補しか見ないので、着くのはそれ以上縮められない反例で、最小の反例とは限りません。x >> 1 の候補を見落とすと、上の3個が元の位置に残った 0xD000_0000、10進数の 3489660928 を答えます。