The problem
Add two integers without using + or −.
Input: a = 5, b = −7 Output: −2
Picture it
Picture two switch panels added column by column. XOR gives each column’s sum without carries (1 + 1 = 0). AND finds the columns where both are 1, which produce a carry spark that jumps one column to the left. Repeat with (sum without carries, carries shifted left) until there are no more carries.
How to recognise it
- You must add without
+or-, so the only tools are bit operators:^,&,<<,>>,~. - Binary addition splits into two parts: the sum without carries (that is XOR) and the carries (that is AND, moved one place left).
- Negative numbers are involved, so you need the 32-bit two's complement view: a fixed width where the top bit means negative.
- Inputs are between −1000 and 1000 on LeetCode, so speed is never the issue; correctness with negatives is.
Start with brute force
Do what a hardware adder does: walk the 32 bit positions from right to left, computing each output bit and the carry into the next position.
def add_ripple(a, b):
M = 0xFFFFFFFF
a, b = a & M, b & M
out, carry = 0, 0
for i in range(32): # one bit position at a time
x, y = (a >> i) & 1, (b >> i) & 1
out |= (x ^ y ^ carry) << i
carry = (x & y) | (carry & (x ^ y))
if out > 0x7FFFFFFF:
out = ~(out ^ M)
return out
This always takes 32 steps, O(1) for fixed width, so it is not slow. It handles one bit at a time, while the shown code handles all 32 positions in each round.
From brute force to the idea
- Find the waste. The ripple loop processes one position per step even though
^and&work on all 32 positions at once. - Split the sum.
a ^ badds every position while ignoring carries.(a & b) << 1is where a carry is created (both bits 1), moved to the position it carries into. - Add the carries in. The true sum is (sum without carry) + (carry). That is another addition, so repeat with
a = a ^ bandb = carryuntil no carry is left (b == 0). - Keep it 32 bits. Python integers have unlimited width, so a negative number has infinitely many leading 1 bits, and without a limit the carry can move left forever.
& M(32 one bits) after each step keeps everything inside 32 bits. Each round moves the lowest carry bit at least one place left, so there are at most 32 rounds. - Read the sign back. If the result's top bit is set (above
0x7FFFFFFF), it stands for a negative number.a ^ Mflips the 32 low bits and~flips everything, which sets all the infinite upper bits: the Python negative value.
This is the key idea: sum = XOR (no carry) plus AND shifted left (the carry), repeated until the carry is 0, all masked to 32 bits.
The key idea
sum = a ^ b, carry = (a & b) << 1; repeat until carry is 0. Python integers have no fixed width, so a negative number acts like endless 1-bits and the carry never dies out: mask every step with M = 0xFFFFFFFF to stay in 32 bits, and at the end turn a pattern with the top bit on back into a negative with ~(a ^ M).
Python solution
def get_sum(a, b):
M = 0xFFFFFFFF # 32 one-bits
a, b = a & M, b & M # 32-bit view
while b:
carry = ((a & b) << 1) & M
a = (a ^ b) & M # add, no carry
b = carry
if a > 0x7FFFFFFF: # top bit on:
a = ~(a ^ M) # it is negative
return aIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Ripple-carry loop | O(32): one step per bit position | O(1) |
| XOR and carry rounds (shown code) | O(32) worst case: at most 32 rounds, usually far fewer | O(1) |
Edge cases
- The example
get_sum(5, -7): returns −2. - Opposite numbers (
-1and1): the carry runs through all 32 positions, taking 32 rounds, and the result is 0. - Zero:
get_sum(0, 0)is 0; the loop does not run. - Results outside 32 bits wrap around like a real 32-bit integer:
get_sum(2**31 - 1, 1)returns −2147483648. With LeetCode's inputs (±1000) this never happens.
Common mistakes
- Leaving out the
& Mmasks in Python:get_sum(-1, 1)then never finishes, because the carry keeps moving into ever-higher bits. - Forgetting the final sign step, so negative results come back as large positive numbers (5 + (−7) gives 4294967294).
- Using
a + borsum([a, b]), which breaks the rule of the problem. - Shifting the carry before the AND (
(a << 1) & b), which builds the wrong carry.
Compute a − b without + or -, for 32-bit integers. You may call get_sum. Describe your approach, then write it if you like.
Compare with our answer
In two's complement, −b equals ~b + 1 (flip every bit, then add 1). So a − b = a + ~b + 1, and both additions can be done with get_sum. The literal 1 is a number, not a minus sign.
def get_diff(a, b):
return get_sum(get_sum(a, ~b), 1) # a - b = a + (~b) + 1
get_diff(5, 7) is −2. Time O(32), space O(1). Results outside 32 bits wrap around, just as for get_sum.
A strong answer mentions: two's complement negation as "flip and add one", reusing the adder twice, and the same 32-bit wrap-around.
1. You must multiply two non-negative integers without *, using only bit operators and an adder. Which approach fits best?
Each 1 bit of b at position i contributes a × 2^i, which is a << i, so about 32 additions suffice. Adding a b times can take billions of steps, and the XOR and AND tricks do not multiply.
2. Why does the shown code apply & M inside the loop in Python?
Python integers are unbounded, and a negative number has infinitely many 1 bits; without the mask, adding −1 and 1 moves the carry left forever. Masking makes the arithmetic behave like a 32-bit register. The sign is restored at the end.
3. A learner deletes the last two lines before return a (the sign check). What does get_sum(5, -7) return?
The bits are right (0xFFFFFFFE), but read without the sign step they are the unsigned value 2^32 − 2. ~(a ^ M) turns that pattern back into −2.
Score 60% or more and the lesson is marked complete.