Calculate the sum of two integers a and b, but you are not allowed to use the operator
Given a = 1 and b = 2, return 3.
First keep in mind that “+/-” cannot be used anywhere.
The key ideas are bitwise operations and recursion:
- Bitwise operations:
- “^” / xor is to remove the same bits and keep the distinct bits, actually like single bit adds of 0 + 1 = 1; here it’s like doing addition for different bits, so that only same bits 0 + 0/1 + 1 are left
- since 0 + 0 has no effects on results, so only care about 1 + 1; this generates the carry. To get the correct bit location of carry, a left shift is needed, which means
(a&b) << 1
- to generate the ^ plus carry, without using “+”. Use recursion to repeatedly add the above two bit operations