Example 1
ready- Input
a = 1 b = 2- Expected
3- Why
- one XOR round plus its carry produces 3
Sum of Two Integers
35 min · getSum()mediumOpen in LeetCode #371 ↗
An adder circuit doesn't own a + key. It combines electrical bits, passes each carry
to the next position, and still gets the same total.
Given two integers a and b, return their sum without using the + or - operators.
You may use bitwise operations. Work with signed 32-bit behavior:
- XOR combines two bits without carrying.
- AND finds positions that need a carry — a value transferred into the next binary
position when both current bits are
1. - Negative values use two's complement, the standard signed-binary encoding where the highest bit marks a negative number.
Constraints
-1_000 <= a, b <= 1_000- The result fits in a signed 32-bit integer.
- Your solution must not use the
+or-operators.
Hints
Split one addition into two jobs
a ^ b gives the partial sum where carries are ignored. a & b marks every
position where both inputs had a 1.
Move the carry
Shift (a & b) left by one. That shifted value is the carry still waiting to be
added. Repeat with the partial sum until no carry remains.
Bound Python's bits
Python integers have no fixed width, so a negative value behaves as if it had
infinitely many leading 1s. Masking to 32 bits means keeping only the lowest
32 positions; do that after every step, then reinterpret bit 31 as a sign at the end.
Follow-up
Can you explain why the carry must become zero within 32 rounds, even when one or both inputs are negative?
Visible cases
Examples
Example 2
ready- Input
a = -2 b = 3- Expected
1- Why
- the 32-bit carry process works across zero
Example 3
ready- Input
a = -5 b = -7- Expected
-12- Why
- two negative two's-complement values still add normally
Interview signal
Asked at
AmazonGoogleBloomberg
Bit-by-bit full adder
A full adder is a tiny circuit that combines two input bits and an incoming carry. Its output bit is their XOR; its outgoing carry is set when at least two of those three bits are set.
Scan a 32-bit mask from right to left and apply that three-input rule at every position. The final carry beyond bit 31 is discarded, matching signed 32-bit behavior.
def get_sum(a: int, b: int) -> int:
mask_32 = 0xFFFFFFFF
sign_bit = 1 << 31
a &= mask_32
b &= mask_32
result = 0
carry = 0
bit = 1
while bit:
bit_a = 1 if a & bit else 0
bit_b = 1 if b & bit else 0
sum_bit = bit_a ^ bit_b ^ carry
if sum_bit:
result |= bit
carry = (bit_a & bit_b) | (bit_a & carry) | (bit_b & carry)
bit = (bit << 1) & mask_32
return result if result < sign_bit else ~(result ^ mask_32)Time O(32). Space O(1) — every bit position is visited once.
XOR carry propagation
The same circuit can process all positions in parallel:
a ^ bis the partial sum without carries.(a & b) << 1is the carry, moved to the position where it belongs.
Replace the two inputs with those two values and repeat. Every round pushes unresolved carries left. Once the carry is zero, the partial sum is final.
def get_sum(a: int, b: int) -> int:
mask_32 = 0xFFFFFFFF
sign_bit = 1 << 31
a &= mask_32
b &= mask_32
while b:
partial = (a ^ b) & mask_32
carry = ((a & b) << 1) & mask_32
a, b = partial, carry
return a if a < sign_bit else ~(a ^ mask_32)The mask is essential in Python. Python integers are unbounded, so a negative value has
conceptually endless leading 1 bits; without & mask_32, the carry may never vanish.
The final expression converts an unsigned 32-bit pattern back to its signed meaning
without using subtraction.
TypeScript and Java bitwise operators already coerce their work to signed 32-bit values.
In C, use the unsigned 32-bit type uint32_t so the same truncation is defined, then
interpret the finished bit pattern as the signed result.
Time O(32). Space O(1) — a carry can move left at most 32 positions.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite