253. overflowing_add — Wrap, But Know It Happened

This morning’s Wrapping<T> (bite 252) wraps silently — but multiword arithmetic needs the carry bit too. overflowing_add returns both: the wrapped result and whether it wrapped.

The sum < a trick

The classic way to detect a carry after unsigned addition compares the result to an input:

1
2
3
4
5

fn add_with_carry(a: u64, b: u64) -> (u64, u64) {
    let sum = a.wrapping_add(b);
    let carry = (sum < a) as u64; // wrapped iff smaller
    (sum, carry)
}

It works — unsigned overflow means the sum came back smaller — but it’s a puzzle for the reader, it’s easy to compare against the wrong operand, and the signed version of the trick is different and wrong in edge cases.

overflowing_add says it directly

Every integer type has overflowing_add (and _sub, _mul, _neg, _shl…): it returns (wrapped_value, overflowed: bool) in one call:

1
2

assert_eq!(u64::MAX.overflowing_add(1), (0, true));
assert_eq!(1_u64.overflowing_add(1), (2, false));

That makes carry chains — the core of any 128-bit-or-wider addition — read like what they are:

1
2
3
4
5
6
7
8

// [lo, hi] little-endian u128 as two u64 limbs
fn add128(a: [u64; 2], b: [u64; 2]) -> [u64; 2] {
    let (lo, carry) = a[0].overflowing_add(b[0]);
    let hi = a[1]
        .wrapping_add(b[1])
        .wrapping_add(carry as u64);
    [lo, hi]
}

1
2
3

let max = [u64::MAX, 0];      // u64::MAX
let one = [1, 0];
assert_eq!(add128(max, one), [0, 1]); // 2^64

One family, four answers to overflow

Where checked_add (and bite 219’s checked_add_signed) bails out with None and Wrapping<T> (bite 252) wraps silently, overflowing_add is the “do both” option: you always get the mod-2^n result, plus the fact you’d otherwise have to reverse-engineer. (The dedicated carrying_add that takes and returns a carry is still nightly-only — on stable, overflowing_add is how the limbs get added.)

Compilers recognize the pattern, too: the carry chain above compiles down to an add + adc pair on x86-64 — the same code the manual trick produces, minus the puzzle.