Discussion on: [Challenge] Add numbers without (+-*/)

[Sean Williams]

I spent an unfortunate amount of time on this...

fn add(a: u32, b: u32) -> u32 {
    let mut carry = false;
    let mut result = 0;
    for i in 0..32 {
        let mask = 1 << i;
        let a_in = (a & mask) > 0;
        let b_in = (b & mask) > 0;
        let s =
            match (a_in, b_in, carry) {
                (false, false, true) => 1,
                (false, true, false) => 1,
                (true, false, false) => 1,
                (true, true, true) => 1,
                _ => 0,
            } << i;
        result = result | s;
        carry =
            match (a_in, b_in, &carry) {
                (false, true, true) => true,
                (true, false, true) => true,
                (true, true, false) => true,
                (true, true, true) => true,
                _ => false,
            };
    }
    result
}

fn main() {
    let a = 10521;
    let b = 830127;
    println!("the usual algorithm: {} + {} = {}", a, b, a + b);
    println!("the funky algorithm: {} + {} = {}", a, b, add(a, b));
}

Output:

the usual algorithm: 10521 + 830127 = 840648
the funky algorithm: 10521 + 830127 = 840648

This currently only works on unsigned integers. I don't feel like spending the time now to remember how two's complement works.

[Sean Williams]

Though I guess I'll be a bit more pedantic with this one: for i in 0..32 smuggles in some integer addition. So here's the set theoretic implementation, which has—less reliance on plus signs:

#[derive(Debug)]
enum Num {
    S(Box<Num>),
    Z,
}

fn s(n: Num) -> Num {
    Num::S(Box::new(n))
}

fn z() -> Num {
    Num::Z
}

fn set_add(a: Num, b: Num) -> Num {
    let mut result = a;
    let mut work = b;
    loop {
        match work {
            Num::S(next) => {
                result = s(result);
                work = *next;
            },
            Num::Z => return result,
        }
    }
}

fn main() {
    let a = s(s(s(z()))); // i.e., 3
    let b = s(s(s(s(s(z()))))); // i.e., 5
    println!("3 + 5 = {:?}", set_add(a, b));
}

Output:

3 + 5 = S(S(S(S(S(S(S(S(Z))))))))

Z means zero, and S means increment. So this is zero incremented eight times.