Adding Integers Without Plus or Minus

Problem: Add two int values without using + or -.

Core Idea

XOR ^ gives us addition without carry. We handle carries in two cases: when both bits are 1, or when one bit is 0, the other is 1, and we have a previous carry. We shift carries forward using bit shift operations.

int getSum(int a, int b) {
    int sum=0,carry=0;
    for(unsigned mask=1;mask!=0;mask<<=1) {
        sum |= (a^b^carry) & mask;
        carry=((a&b) | (a^b)&carry)<<1;
    }
    return sum;
}

Recursive Solution

If a and b are binary numbers, then a+b = a^b + (a&b)<<1. When b equals 0, the sum is just the other number.

int getSum(int a, int b) {
    if (b==0) return a;
    int sum=a^b;
    int carry=(a&b)<<1;
    return getSum(sum, carry);
}

What I Learned

• The connection between bitwise operations and basic arithmetic