Sum of Two Integers

Intuition

We can simply use a+b, but in this problem, we cannot use + or -. So, we use bit manipulation to do it.

We use recursive to solve this problem.

We have b == 0 as terminate point, and we call the function with a^b and (a&b)<<1.

So, a + b == newA + newB, and b will reach 0 eventually, thus we find the answer.

A Peek of the code

cpp

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

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sum of Two Integers.

Examples

Will show a,b value's change in runtime.

Example 1:

Input: a = 1, b = 2
Output: 3

1 2  (a,b)
00000000000000000000000000000001 (bitwise a)
00000000000000000000000000000010 (bitwise b)
3 0
00000000000000000000000000000011
00000000000000000000000000000000

Example 2:

Input: a = -1, b = -2
Output: -3

-1 -2
11111111111111111111111111111111
11111111111111111111111111111110
1 -4
00000000000000000000000000000001
11111111111111111111111111111100
-3 0
11111111111111111111111111111101
00000000000000000000000000000000

Example 3:

Input: a = -1000, b = 1000
Output: 0

-1000 1000
11111111111111111111110000011000
00000000000000000000001111101000
-16 16
11111111111111111111111111110000
00000000000000000000000000010000
-32 32
11111111111111111111111111100000
00000000000000000000000000100000
-64 64
11111111111111111111111111000000
00000000000000000000000001000000
-128 128
11111111111111111111111110000000
00000000000000000000000010000000
-256 256
11111111111111111111111100000000
00000000000000000000000100000000
-512 512
11111111111111111111111000000000
00000000000000000000001000000000
-1024 1024
11111111111111111111110000000000
00000000000000000000010000000000
-2048 2048
11111111111111111111100000000000
00000000000000000000100000000000
-4096 4096
11111111111111111111000000000000
00000000000000000001000000000000
-8192 8192
11111111111111111110000000000000
00000000000000000010000000000000
-16384 16384
11111111111111111100000000000000
00000000000000000100000000000000
-32768 32768
11111111111111111000000000000000
00000000000000001000000000000000
-65536 65536
11111111111111110000000000000000
00000000000000010000000000000000
-131072 131072
11111111111111100000000000000000
00000000000000100000000000000000
-262144 262144
11111111111111000000000000000000
00000000000001000000000000000000
-524288 524288
11111111111110000000000000000000
00000000000010000000000000000000
-1048576 1048576
11111111111100000000000000000000
00000000000100000000000000000000
-2097152 2097152
11111111111000000000000000000000
00000000001000000000000000000000
-4194304 4194304
11111111110000000000000000000000
00000000010000000000000000000000
-8388608 8388608
11111111100000000000000000000000
00000000100000000000000000000000
-16777216 16777216
11111111000000000000000000000000
00000001000000000000000000000000
-33554432 33554432
11111110000000000000000000000000
00000010000000000000000000000000
-67108864 67108864
11111100000000000000000000000000
00000100000000000000000000000000
-134217728 134217728
11111000000000000000000000000000
00001000000000000000000000000000
-268435456 268435456
11110000000000000000000000000000
00010000000000000000000000000000
-536870912 536870912
11100000000000000000000000000000
00100000000000000000000000000000
-1073741824 1073741824
11000000000000000000000000000000
01000000000000000000000000000000
-2147483648 -2147483648
10000000000000000000000000000000
10000000000000000000000000000000
0 0
00000000000000000000000000000000
00000000000000000000000000000000

Sum of Two Integers ​

Intuition ​

A Peek of the code ​

Examples ​

Sum of Two Integers

Intuition

A Peek of the code

Examples