Sum of Two Integers (LeetCode 371)
You get two integers, a and b. Return their sum. The code may not use the + operator or the - operator anywhere.
The only tools left are the bitwise operators and shifts, which work on the binary digits of a number.
Worked Examples
a = 1, b = 231 is 01 and 2 is 10. No place has a 1 in both numbers, so there is no carry, and the sum without carries is 11, which is 3.a = 2, b = 352 is 010 and 3 is 011. The sum without carries is 001. Both numbers have a 1 in place 1, which makes a carry into place 2. Adding the carry 100 gives 101, which is 5.⚖️Formal Constraints & Bounds
-1000 <= a, b <= 1000The operators
+and-must not be used
Core Insight
In binary addition, a place where only one number has a 1 gives a sum bit of 1, and a place where both numbers have a 1 gives a sum bit of 0 and a carry into the next place. a ^ b is every sum bit without carries, and (a & b) << 1 is every carry, already in the place where it belongs. Their sum is the answer, so repeat with the carries as the new second number. Each round moves every carry at least one place left, so within 32 rounds nothing is left to carry.
Real-World Scenario & Production Applications
A processor adds two numbers with a chain of small adders, one for each binary place. Each adder produces a sum bit with XOR and a carry bit with AND, and passes the carry to the next place on the left.
Step-by-Step Execution Trace Table
Trace of Example 2: a = 2, b = 3. Small numbers, so the 32-bit mask changes nothing.
| Step | a | b | total = a ^ b | carry = (a & b) << 1 |
|---|---|---|---|---|
| start | 010 (2) | 011 (3) | ||
| round 1 | 010 (2) | 011 (3) | 001 (1) | 100 (4) |
| round 2 | 001 (1) | 100 (4) | 101 (5) | 000 (0) |
| end | 101 (5) | 000 (0) |
After round 2, b is 0, so a = 5 is the sum.
A negative example: a = -5, b = -3. After the mask, a is 4294967291 and b is 4294967293. The loop ends with a = 4294967288, which has bit 31 set. The last line turns it into ~(4294967288 ^ 4294967295) = ~7 = -8.
| 1 | a, b = a & mask, b & mask |
| 2 | while b: |
| 3 | total = (a ^ b) & mask |
| 4 | carry = ((a & b) << 1) & mask |
| 5 | a, b = total, carry |
| 6 | return a if a <= sign_max else ~(a ^ mask) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Adding in binary works place by place. In a place where only one number has a 1, the sum is 1. Where both have a 1, the sum is 0 and a carry of 1 goes to the next place on the left. The XOR a ^ b is the sum of every place without the carries. The AND a & b marks the places that make a carry, and shifting it left by 1 moves each carry to the place where it belongs. Adding those two numbers is the same problem again, but the carries have moved one place to the left.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number with shifts and masks. Here two numbers are combined with XOR and AND, and the loop while b repeats until the carries are gone. The mask keeps both numbers in 32 bits, and the last line turns the 32-bit pattern back into a signed number.
🔑 The Key Idea in the Code
Each round, every carry moves at least one place left. After at most 32 rounds the carries have left the 32-bit word, so b is 0 and a is the sum. A negative Python integer has no fixed width, so without mask the loop can run forever.
Using no 32-bit mask in Python: a negative Python integer has no fixed width, so for
a = -1andb = 1the carry moves left forever andbnever becomes 0. The loop never ends.Not shifting the carry one place left:
(a & b)without<< 1adds the carry back into the same place. Fora = 2andb = 3the result is 3, where 5 is right.Returning
awithout converting it back to a signed value: fora = -5andb = -3the result is 4294967288, where -8 is right.Running one round instead of looping until
bis 0: the carry of one round can cause another carry. Fora = 2andb = 3, one round returns 1, where 5 is right.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Sum of two integers without + or -": the operators for adding are not allowed, so the addition must be built from bit operators. XOR gives the sum of each place without carries, and AND shifted left gives the carries.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
a + b equals the original sum, modulo 2 ** 32, after every round. a ^ b plus (a & b) << 1 equals a + b, so setting a = total and b = carry keeps the sum. When b is 0, a is the sum.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A carry that is not shifted left:
2 + 3returns 3, because the carry is added into the same place it came from.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Carry Add. Binary addition has two parts. The sum of each place without carries is a XOR b. The carries are a AND b, shifted left by one, because a carry goes to the next place. Their sum is the answer, so I repeat with the carries as the new b until b is 0. In Python I cut every value to 32 bits with a mask, because a negative Python integer has no fixed width and its carry would never leave. At the end I turn the 32-bit pattern back into a signed value: if it is above the largest signed value, I flip its bits and invert the result. For 2 and 3, round one gives 1 and 4, round two gives 5 and 0, and the answer is 5. Each round moves every carry at least one place left, so there are at most 32 rounds. That is O of 1 time and O of 1 space.
Complexity & Mathematical Proof
O(1)
Look at the loop. Each round replaces b by the carries, and every carry sits at least one place to the left of the place that made it. After 32 rounds every carry is past bit 31, and mask removes it, so b is 0. The loop runs at most 32 times, whatever the values of a and b, so time is O(1). Written with the word size w, it is O(w).
O(1)
The code keeps six integers, mask, sign_max, a, b, total and carry, whatever the input. There is no table and no recursion, so space is O(1).
Derivation Progression
Every carry moves at least one place left per round and leaves the word after bit 31.
5 = O(1)
One XOR, one AND, one shift and two masks.
Rounds times a constant amount of work.
Variable Definitions
The word width, 32 bits
The places where both numbers have a 1, moved one place left
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): six integers
O(1): one integer
Boundary Best / Worst Cases
: one of the numbers is 0, so the loop does not run.
.
: 32 rounds, for example a = -1 and b = 1.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The prompt asks for the "sum of two integers without using + and -". Binary addition works place by place: a ^ b is the sum of every place without carries, and (a & b) << 1 holds the carries, each moved one place to the left. Repeating the step with the carries as the new second number adds them in.
. Each round moves every carry at least one place to the left, so the carries leave a 32-bit word after at most 32 rounds. Time is and space is .
Without mask, a negative Python integer never loses its carry: -1 + 1 never ends. Without << 1, the carry is added back into the same place: 2 + 3 returns 3. Without the last line, -5 + -3 returns 4294967288 instead of -8.
Sum of Two Integers (LeetCode 371)
You get two integers, a and b. Return their sum. The code may not use the + operator or the - operator anywhere.
The only tools left are the bitwise operators and shifts, which work on the binary digits of a number.
Worked Examples
a = 1, b = 231 is 01 and 2 is 10. No place has a 1 in both numbers, so there is no carry, and the sum without carries is 11, which is 3.a = 2, b = 352 is 010 and 3 is 011. The sum without carries is 001. Both numbers have a 1 in place 1, which makes a carry into place 2. Adding the carry 100 gives 101, which is 5.⚖️Formal Constraints & Bounds
-1000 <= a, b <= 1000The operators
+and-must not be used
Core Insight
In binary addition, a place where only one number has a 1 gives a sum bit of 1, and a place where both numbers have a 1 gives a sum bit of 0 and a carry into the next place. a ^ b is every sum bit without carries, and (a & b) << 1 is every carry, already in the place where it belongs. Their sum is the answer, so repeat with the carries as the new second number. Each round moves every carry at least one place left, so within 32 rounds nothing is left to carry.
Real-World Scenario & Production Applications
A processor adds two numbers with a chain of small adders, one for each binary place. Each adder produces a sum bit with XOR and a carry bit with AND, and passes the carry to the next place on the left.
Step-by-Step Execution Trace Table
Trace of Example 2: a = 2, b = 3. Small numbers, so the 32-bit mask changes nothing.
| Step | a | b | total = a ^ b | carry = (a & b) << 1 |
|---|---|---|---|---|
| start | 010 (2) | 011 (3) | ||
| round 1 | 010 (2) | 011 (3) | 001 (1) | 100 (4) |
| round 2 | 001 (1) | 100 (4) | 101 (5) | 000 (0) |
| end | 101 (5) | 000 (0) |
After round 2, b is 0, so a = 5 is the sum.
A negative example: a = -5, b = -3. After the mask, a is 4294967291 and b is 4294967293. The loop ends with a = 4294967288, which has bit 31 set. The last line turns it into ~(4294967288 ^ 4294967295) = ~7 = -8.
| 1 | a, b = a & mask, b & mask |
| 2 | while b: |
| 3 | total = (a ^ b) & mask |
| 4 | carry = ((a & b) << 1) & mask |
| 5 | a, b = total, carry |
| 6 | return a if a <= sign_max else ~(a ^ mask) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Adding in binary works place by place. In a place where only one number has a 1, the sum is 1. Where both have a 1, the sum is 0 and a carry of 1 goes to the next place on the left. The XOR a ^ b is the sum of every place without the carries. The AND a & b marks the places that make a carry, and shifting it left by 1 moves each carry to the place where it belongs. Adding those two numbers is the same problem again, but the carries have moved one place to the left.
➗ What Is Added To Bit Tricks
Bit Tricks moves the bits of one number with shifts and masks. Here two numbers are combined with XOR and AND, and the loop while b repeats until the carries are gone. The mask keeps both numbers in 32 bits, and the last line turns the 32-bit pattern back into a signed number.
🔑 The Key Idea in the Code
Each round, every carry moves at least one place left. After at most 32 rounds the carries have left the 32-bit word, so b is 0 and a is the sum. A negative Python integer has no fixed width, so without mask the loop can run forever.
Using no 32-bit mask in Python: a negative Python integer has no fixed width, so for
a = -1andb = 1the carry moves left forever andbnever becomes 0. The loop never ends.Not shifting the carry one place left:
(a & b)without<< 1adds the carry back into the same place. Fora = 2andb = 3the result is 3, where 5 is right.Returning
awithout converting it back to a signed value: fora = -5andb = -3the result is 4294967288, where -8 is right.Running one round instead of looping until
bis 0: the carry of one round can cause another carry. Fora = 2andb = 3, one round returns 1, where 5 is right.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Sum of two integers without + or -": the operators for adding are not allowed, so the addition must be built from bit operators. XOR gives the sum of each place without carries, and AND shifted left gives the carries.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
a + b equals the original sum, modulo 2 ** 32, after every round. a ^ b plus (a & b) << 1 equals a + b, so setting a = total and b = carry keeps the sum. When b is 0, a is the sum.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A carry that is not shifted left:
2 + 3returns 3, because the carry is added into the same place it came from.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Carry Add. Binary addition has two parts. The sum of each place without carries is a XOR b. The carries are a AND b, shifted left by one, because a carry goes to the next place. Their sum is the answer, so I repeat with the carries as the new b until b is 0. In Python I cut every value to 32 bits with a mask, because a negative Python integer has no fixed width and its carry would never leave. At the end I turn the 32-bit pattern back into a signed value: if it is above the largest signed value, I flip its bits and invert the result. For 2 and 3, round one gives 1 and 4, round two gives 5 and 0, and the answer is 5. Each round moves every carry at least one place left, so there are at most 32 rounds. That is O of 1 time and O of 1 space.
Complexity & Mathematical Proof
O(1)
Look at the loop. Each round replaces b by the carries, and every carry sits at least one place to the left of the place that made it. After 32 rounds every carry is past bit 31, and mask removes it, so b is 0. The loop runs at most 32 times, whatever the values of a and b, so time is O(1). Written with the word size w, it is O(w).
O(1)
The code keeps six integers, mask, sign_max, a, b, total and carry, whatever the input. There is no table and no recursion, so space is O(1).
Derivation Progression
Every carry moves at least one place left per round and leaves the word after bit 31.
5 = O(1)
One XOR, one AND, one shift and two masks.
Rounds times a constant amount of work.
Variable Definitions
The word width, 32 bits
The places where both numbers have a 1, moved one place left
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): six integers
O(1): one integer
Boundary Best / Worst Cases
: one of the numbers is 0, so the loop does not run.
.
: 32 rounds, for example a = -1 and b = 1.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The prompt asks for the "sum of two integers without using + and -". Binary addition works place by place: a ^ b is the sum of every place without carries, and (a & b) << 1 holds the carries, each moved one place to the left. Repeating the step with the carries as the new second number adds them in.
. Each round moves every carry at least one place to the left, so the carries leave a 32-bit word after at most 32 rounds. Time is and space is .
Without mask, a negative Python integer never loses its carry: -1 + 1 never ends. Without << 1, the carry is added back into the same place: 2 + 3 returns 3. Without the last line, -5 + -3 returns 4294967288 instead of -8.