Namaran

Code daily. Without assist.

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。

  1. u64 に広げて u64::from(x) + u64::from(y) + u64::from(carry) を計算し、下位32ビットを桁に、上位32ビットを繰り上がりにする書き方でも直ります。