Add Two Numbers Without Plus
Problem
A tiny chip exposes only bitwise instructions: AND, OR, XOR and shifts. Write the addition routine it needs: given two 32-bit signed integers a and b, return a + b without using + or - on them. Both inputs and the sum lie between -1,000 and 1,000, and the result must match ordinary 32-bit two's complement addition, including for negative numbers.
Examples
Input: a = 1, b = 2
Output: 3Input: a = -5, b = 3
Output: -2Input: a = -7, b = -8
Output: -15
Why: edge case, both inputs are negativeHints
0 / 3
Add two bits by hand: the digit you write down is their XOR, and a carry appears only when both bits are 1, which is their AND.
So a ^ b is the sum without carries, and (a & b) << 1 is the carries moved to the column they belong to. Adding those two is the same problem again, with fewer carries each round.
Python integers never overflow, so a negative number has infinitely many leading 1 bits. Keep every step inside 32 bits with a mask, and at the end turn a value above 0x7FFFFFFF back into a negative number.
Solution
Binary addition splits into two independent parts: XOR gives each column's digit ignoring carries, and AND shifted left by one gives the carries in the column they flow into. The true sum is those two numbers added together, so the loop repeats with them until no carry is left, and each round pushes every remaining carry at least one column to the left, so a 32-bit add finishes in at most 32 rounds. Python integers are unbounded, so every intermediate is masked to 32 bits, which reproduces the wraparound of a real register. At the end a value with bit 31 set is a negative number in two's complement, and ~(a ^ MASK) converts it back to Python's negative integer. Time and space are both O(1) for a fixed 32-bit width.
MASK, MAX_INT = 0xFFFFFFFF, 0x7FFFFFFF
def add(a, b):
while b & MASK:
a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK # digits, then carries
a &= MASK
return a if a <= MAX_INT else ~(a ^ MASK) # bit 31 set means negative
print(add(1, 2)) # -> 3
print(add(-5, 3)) # -> -2
print(add(-7, -8)) # -> -15
print(add(0, -4)) # -> -4Stuck on the idea rather than the code? Binary and Bitwise Ops covers it.