Sum of Two Integers
Sum of Two Integers is a medium bit manipulation problem solved with the basics pattern.
The best approach, optimal (xor plus carry loop), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bit-by-bit full adder up.
Problem
Given two integers a and b, return their sum without using the + or - operators.
You have to build the addition yourself from bitwise operations. Treat the numbers as 32-bit two’s complement integers, so negative inputs must work too.
Examples
Example 1
- Input
a = 4, b = 9- Output
13- Why
- 0100 + 1001 has no overlapping 1-bits, so the sum is just the XOR: 1101 = 13.
Example 2
- Input
a = -7, b = 3- Output
-4- Why
- Negative numbers are stored in two's complement, and the same bit rules still give the right answer.
Example 3
- Input
a = -5, b = -6- Output
-11- Why
- Both inputs are negative; carries ripple through the high bits and the result stays negative.
Constraints
-1000 <= a, b <= 1000- Do not use the
+or-operators to combineaandb.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Bit-by-bit full adder | O(1) | O(1) |
| Optimal (XOR plus carry loop) | O(1) | O(1) |
1Bit-by-bit full adder
O(1)Always exactly 32 iterations.O(1)A few integer variables.Simulate a hardware ripple-carry adder. Walk over the 32 bit positions from lowest to highest, take bit i of both numbers and the incoming carry, and compute the sum bit with XOR and the outgoing carry with AND/OR. Two's complement makes negative numbers work automatically.
- Set result = 0 and carry = 0.
- For i from 0 to 31: x = bit i of a, y = bit i of b.
- sum bit = x ^ y ^ carry; carry = (x & y) | (x & carry) | (y & carry).
- Set bit i of result to the sum bit.
class Solution {
public int getSum(int a, int b) {
int result = 0, carry = 0;
for (int i = 0; i < 32; i++) {
int x = (a >>> i) & 1;
int y = (b >>> i) & 1;
int s = x ^ y ^ carry;
carry = (x & y) | (x & carry) | (y & carry);
result |= s << i;
}
return result;
}
}class Solution:
def getSum(self, a: int, b: int) -> int:
result, carry = 0, 0
for i in range(32):
x = (a >> i) & 1
y = (b >> i) & 1
s = x ^ y ^ carry
carry = (x & y) | (x & carry) | (y & carry)
result |= s << i
# reinterpret the 32-bit pattern as a signed number
return result if result <= 0x7FFFFFFF else ~(result ^ 0xFFFFFFFF)class Solution {
public:
int getSum(int a, int b) {
unsigned ua = a, ub = b, result = 0, carry = 0;
for (int i = 0; i < 32; i++) {
unsigned x = (ua >> i) & 1u;
unsigned y = (ub >> i) & 1u;
unsigned s = x ^ y ^ carry;
carry = (x & y) | (x & carry) | (y & carry);
result |= s << i;
}
return (int)result;
}
};function getSum(a, b) {
let result = 0, carry = 0;
for (let i = 0; i < 32; i++) {
const x = (a >>> i) & 1;
const y = (b >>> i) & 1;
const s = x ^ y ^ carry;
carry = (x & y) | (x & carry) | (y & carry);
result |= s << i;
}
return result;
}2Optimal (XOR plus carry loop)
O(1)At most 32 rounds, since the carry moves left every round.O(1)Only a couple of integers.Work on all bits at once. a ^ b adds every position without carries, and (a & b) << 1 is the carry that each position pushes to the next one. Replace a with the partial sum and b with the carries, and repeat until no carry remains. Each round moves the carries at least one position left, so it ends within 32 rounds.
- While b != 0: carry = (a & b) << 1; a = a ^ b; b = carry.
- Return a.
- In Python, keep both values masked to 32 bits and convert the final pattern back to a signed number.
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
}class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
a &= mask
b &= mask
while b:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
return a if a <= 0x7FFFFFFF else ~(a ^ mask)class Solution {
public:
int getSum(int a, int b) {
unsigned ua = a, ub = b;
while (ub != 0) {
unsigned carry = (ua & ub) << 1;
ua = ua ^ ub;
ub = carry;
}
return (int)ua;
}
};function getSum(a, b) {
while (b !== 0) {
const carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}Edge cases to test
- One of the numbers is 0
- Opposite signs that cancel exactly, like 5 and -5
- Both numbers negative
- In Python, integers are unbounded, so you must mask to 32 bits or the carry loop never ends for negative inputs
Hints
Hint 1
Adding two bits gives a sum bit and a carry bit. Which bitwise operators produce each of them?
Hint 2
For whole numbers: a ^ b is the sum ignoring carries, and (a & b) << 1 is exactly the carries.
Hint 3
Repeat with those two values until there is no carry left.
FAQ
What is the best time complexity for Sum of Two Integers?
Optimal (XOR plus carry loop) runs in O(1) time and O(1) extra space. At most 32 rounds, since the carry moves left every round.
Which pattern does Sum of Two Integers use?
It is a bit manipulation problem that uses the basics pattern. Other problems with the same pattern: Decimal to binary, Convert Binary Number in a Linked List to Integer, K-th Bit is Set or Not.
Is there a brute force solution for Sum of Two Integers?
Yes. Bit-by-bit full adder takes O(1) time and O(1) space. Simulate a hardware ripple-carry adder.
Which edge cases should I test for Sum of Two Integers?
One of the numbers is 0; Opposite signs that cancel exactly, like 5 and -5; Both numbers negative; In Python, integers are unbounded, so you must mask to 32 bits or the carry loop never ends for negative inputs.