2026-09-29
ones.rs
fn ones(mut x: i8) -> u32 {
let mut n = 0;
while x != 0 {
x &= x.wrapping_sub(1);
n += 1;
}
n
}
fn main() {
println!("{} {} {}", ones(6), ones(-6), ones(i8::MIN));
}
これは何を出力するでしょうか?
Answer
2 6 1 です。
x & (x - 1) は、x の最下位の1ビットを消します。x - 1 は最下位の1を0にし、それより下の0をすべて1にするので、元の x との AND では最下位の1とその下だけが0になり、上のビットはそのまま残ります。ループは1のビットを1つずつ消していくので、n は x に含まれる1の個数です。6 は 0000_0110 なので 2 になります。
負の数でも、この操作はビット列に対してそのまま働きます。i8 の -6 は2の補数で 1111_1010 と表され、1が6個あるので 6 です。符号を外した 6 と同じ 2 にはならず、負の数だから 0 に届かず終わらない、ということもありません。1を消し続ければビット列はいずれすべて0になり、x != 0 が偽になります。
i8::MIN は 1000_0000 で、1は1個です。ここで x - 1 と書いていたら、-128 - 1 が i8 の範囲を超え、デバッグビルドでは panic します。wrapping_sub は範囲を超えた分を回り込ませて 0111_1111 を返すので、AND の結果は 0 になり、1回でループを抜けます。-6 の最後の1回も、x が 1000_0000 になったところでこの計算を通っています。