2026-10-01
limbs.rs
fn add(a: &[u32], b: &[u32]) -> Vec<u32> {
let mut out = Vec::new();
let mut carry = 0;
for (&x, &y) in a.iter().zip(b) {
let s = x.wrapping_add(y).wrapping_add(carry);
carry = u32::from(s < x);
out.push(s);
}
out.push(carry);
out
}
fn main() {
// limbs are base 2^32, least significant first
println!("{:?}", add(&[1, 5], &[u32::MAX, u32::MAX]));
}
add は、2^32 進の各桁を下の桁から u32 で並べた2つの整数を、桁数が同じもの同士で足すつもりです。引数も標準入力も使わず、add(&[1, 5], &[u32::MAX, u32::MAX]) の結果を出力します。本来は [0, 5, 1] と出力されるはずが、いまは [0, 5, 0] と出力されます。
Answer
Wrong
let s = x.wrapping_add(y).wrapping_add(carry);
carry = u32::from(s < x);
2つの u32 を wrapping_add で足したとき、和が x より小さくなるのは 2^32 を超えて一周したときだけです。1桁目の 1 + u32::MAX はこの判定どおりに動き、和は 0、0 < 1 なので繰り上がりは 1 になります。
ところが、この判定が成り立つのは足す値が2つのときだけです。2桁目は 5 + u32::MAX + 1 の3つを足し、x に加わる u32::MAX + 1 はちょうど 2^32 で、一周分にあたります。和は x と同じ 5 に戻り、5 < 5 は偽なので、繰り上がりは 0 とされて最上位の 1 が落ちます。
Right
let (s, c1) = x.overflowing_add(y);
let (s, c2) = s.overflowing_add(carry);
carry = u32::from(c1 || c2);
overflowing_add は和と一緒に、一周したかどうかを bool で返します。3つの値を2回に分けて足し、どちらかで一周していれば繰り上がりにします。2回とも一周することはありません。1回目で一周したなら和は u32::MAX - 1 以下なので、そこに繰り上がりの 1 を足しても一周しないからです1。
u64に広げてu64::from(x) + u64::from(y) + u64::from(carry)を計算し、下位32ビットを桁に、上位32ビットを繰り上がりにする書き方でも直ります。