LeetCode 371 · Bit Manipulation · concept: bit-manipulation
Problem
Add two integers without using + or -.
a = 2, b = 3 -> 5
Approach — XOR for sum, AND-shift for carry (optimal)
Rebuild addition from its hardware primitives. For each bit column: a ^ b is the sum ignoring carries, and (a & b) << 1 is the carry into the next column. Repeat until there’s no carry left.
def getSum(a, b):
mask = 0xFFFFFFFF # 32-bit window (Python ints are unbounded)
while b & mask: # while a carry remains
a, b = a ^ b, (a & b) << 1 # sum-without-carry, carry
a &= mask
# interpret as signed 32-bit
return a if a <= 0x7FFFFFFF else ~(a ^ mask)Time O(1) (≤ 32 carry rounds), space O(1).
Full-adder logic
a ^ b sets a bit where exactly one of the inputs has a 1 (sum, no carry); a & b finds where both are 1 (a carry, which belongs one position higher, hence << 1). Looping propagates carries until they run out — precisely how a hardware ripple-carry adder works. In Python the masking is essential because its ints are arbitrary-precision (no natural 32-bit overflow or sign), so you emulate a fixed-width signed word.
Key insight
Addition = XOR (partial sum) + carry (AND, shifted), iterated. This exposes what + actually compiles to, and the same decomposition underlies grade-school arithmetic and ALU design — the deepest “what is a number operation, really” bit problem.
Related
- concept: bit-manipulation
- prev: Missing Number · next: Reverse Integer
Software engineering
Infrastructure & security
Computer science
Hardware & engineering