Sum of two integers

Add two integers without + or -. XOR adds each column and ignores carries; AND then shift left finds the carries. Repeat until no carry is left.

The idea

In one binary column, 0 + 0 = 0, 0 + 1 = 1 and 1 + 1 = 0 carry 1. The no-carry part is exactly XOR. A carry appears only where both bits are 1, which is AND, and it belongs one column to the left, so shift it left by one. Now a + b = (a ^ b) + ((a & b) << 1): the same problem with a new pair. Repeat until the carry is 0; each round the carries move left, so it always ends.

Code

public int GetSum(int a, int b) {
    while (b != 0) { // b holds the carries still to be added
        int sum = a ^ b; // add every column, ignoring carries
        int carry = (a & b) << 1; // a column with two 1s carries into the next column
        a = sum;
        b = carry;
    }
    return a;
}

Tips

• Try a = -3, b = 5. -3 is 11111101 in two's complement; the carry keeps moving left until it falls off the top bit, and what is left is 2. A real int does the same with 32 bits.
• Try a = 6, b = -9: the carry dies after one round, giving -3.
• The drawing uses 8 bits (like sbyte) so every bit fits; a C# int has 32, so its carry can travel further before it falls off, but the answer is the same.

In the .NET library

C# shifts and bitwise operators never throw on overflow, even in a checked context, so (a & b) << 1 quietly drops a carry out of bit 31. Python ints never overflow, so the same loop needs a 0xFFFFFFFF mask there.