The problem
Return a + b without using the operators + or −.
Examples
- Input
a = 1, b = 2
- Output
3
- Input
a = 2, b = 3
- Output
5
Constraints
- −1000 ≤ a, b ≤ 1000
The idea
Adding in binary, each column gives a sum bit and maybe a carry. The sum bits without carries are exactly a ^ b (1 where the bits differ). A carry comes from a column where both bits are 1 — a & b — and belongs one column to the left: (a & b) << 1.
So a + b = (a ^ b) + ((a & b) << 1). That is another addition, so repeat it with those two numbers; each round pushes the carries further left, and they run out within 32 rounds. Negative numbers work unchanged in two’s complement, the way computers store them — in Python, whose integers never overflow, the answer is kept to 32 bits with a mask and its top bit read back as the sign.
- Time
- O(1) — at most 32 rounds
- Space
- O(1)
Solution · every language run against every case
class Solution: def getSum(self, a: int, b: int) -> int: # a ^ b adds without carrying; (a & b) << 1 is the carry. Repeat until no carry is left. # Python's integers never overflow, so keep them to 32 bits with a mask, as other languages do. MASK = 0xFFFFFFFF a, b = a & MASK, b & MASK while b: a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK return a if a < 0x80000000 else ~(a ^ MASK) # read bit 31 as the sign