How to Compute Sum of Two Integers without Plus+ and Minus- Operators?

Your task is to Calculate the sum of two integers a and b without using the operator + and -.

Bit Manipulation

Integers represent in binary consists of bits (e.g. A 32-bit integer contains 32-bit). For example, if we want to add 5 (in binary which is 101) and 3 (in binary which is 011) together, we can:

 101
 011
---
1000

This involves adding each bit from right (least significant) to the left (most significant), with carry-over. We can use exclusive or (^ or xor) to accomplish the result for bits without considering the carry. The carry has to be considered by doing logics AND (&) and shift 1 position to the left. For example, 01 and 01 results in carry 10. (01&01=01, 01 < 1 = 10).

With above method, we can do this using a loop:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int getSum(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        while (b != 0) {
            int carry = a & b;
            a ^= b;
            b = carry << 1;
        }
        return a;
    }
};

class Solution {
public:
    int getSum(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        while (b != 0) {
            int carry = a & b;
            a ^= b;
            b = carry << 1;
        }
        return a;
    }
};

We can also implement this method using recursion:

1
2
3
4
5
6
7
8
9
10
11

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

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

Pointers Math

In C/C++, the expression for a[i] can be written as [a]i and both are evaluated as *(a+i*sizeof(a[0])). Therefore, we can just let the compiler do the addition tricks:

1
2
3
4
5
6

class Solution {
public:
    int getSum(int a, int b) {
        return (long)&((&((char*)NULL)[b])[a]);
    }
};

class Solution {
public:
    int getSum(int a, int b) {
        return (long)&((&((char*)NULL)[b])[a]);
    }
};

The NULL is evaluated to 0. 0[b] is then evaluated to b+0, and the intermediate result is added to a by compiler when accessing the array address.

The principles underlying these two methods are important in understanding low-level (such as assembly) computer knowledge although they may not be so useful in modern programming land e.g. C# .NET.

Mathematic Solution

This works for float numbers as well, however, it may not be so efficient as you need to use log and power functions.

Feature Comments

but……. if all computers are are dding machines at their core, meaning all they can ever do is add, why would you avoid the most cost effective operation possible?

Usually bitwise/shift operators are more simple and efficient on integers, and integer adders are implemented using them at processor level (2’s complement). Although it has no sense to do that at C/C++ level, it’s just a puzzle.

–EOF (The Ultimate Computing & Technology Blog) —