Approach Summary
a ^ b gives sum without carry; (a & b) << 1 gives carry. Repeat until carry = 0.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Bit-by-Bit Full Adder Simulation | O(1) [32 iterations] | O(1) | Inspect individual bits from 0 to 31 with a running carry bit, mimicking digital logic adder hardware. |
| 2 Approach 2: Bitwise XOR + Shift Carry Propagation (Optimal) | O(1) [at most 32 loops] | O(1) | Parallel carry calculation using XOR for addition and AND shifted left by 1 for carries until carry is zero. |
Approach 1: Bit-by-Bit Full Adder Simulation
A digital full adder computes the sum bit and carry bit for position i using bit_a, bit_b, and previous carry: sum_bit = bit_a ^ bit_b ^ carry, and next_carry = (bit_a & bit_b) | (carry & (bit_a ^ bit_b)). We iterate through all 32 bit positions, accumulate the sum bit into a result integer, and pass the carry to the next position. While educational and rigorous, it requires explicitly iterating through all 32 bit slots regardless of the operands.
Approach 1: Bit-by-Bit Full Adder Simulation Implementation
Approach 1: Bit-by-Bit Full Adder Simulation
class Solution {
public int getSum(int a, int b) {
int result = 0;
int carry = 0;
for (int i = 0; i < 32; i++) {
int b1 = (a >> i) & 1;
int b2 = (b >> i) & 1;
int sumBit = b1 ^ b2 ^ carry;
carry = (b1 & b2) | (carry & (b1 ^ b2));
if (sumBit != 0) {
result |= (1 << i);
}
}
return result;
}
}class Solution {
public:
int getSum(int a, int b) {
int result = 0;
int carry = 0;
for (int i = 0; i < 32; i++) {
int b1 = (a >> i) & 1;
int b2 = (b >> i) & 1;
int sumBit = b1 ^ b2 ^ carry;
carry = (b1 & b2) | (carry & (b1 ^ b2));
if (sumBit) {
result |= (1 << i);
}
}
return result;
}
};class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
max_int = 0x7FFFFFFF
result = 0
carry = 0
for i in range(32):
b1 = (a >> i) & 1
b2 = (b >> i) & 1
sum_bit = b1 ^ b2 ^ carry
carry = (b1 & b2) | (carry & (b1 ^ b2))
if sum_bit:
result |= (1 << i)
result &= mask
return result if result <= max_int else ~(result ^ mask)function getSum(a, b) {
let result = 0;
let carry = 0;
for (let i = 0; i < 32; i++) {
const b1 = (a >> i) & 1;
const b2 = (b >> i) & 1;
const sumBit = b1 ^ b2 ^ carry;
carry = (b1 & b2) | (carry & (b1 ^ b2));
if (sumBit) {
result |= (1 << i);
}
}
return result;
}Approach 2: Bitwise XOR + Shift Carry Propagation (Optimal)
XOR (a ^ b) adds bits without taking into account carries (0+0=0, 0+1=1, 1+0=1, 1+1=0). The carry is produced exclusively where both bits are 1, which is given by (a & b). Since the carry belongs to the next higher power of two, we shift it left by 1: carry = (a & b) << 1. In C++, casting to unsigned int avoids undefined behavior when left-shifting negative signed integers. In Python, masking with 0xFFFFFFFF constrains intermediate values to 32 bits.
Approach 2: Bitwise XOR + Shift Carry Propagation (Optimal) Implementation
Approach 2: Bitwise XOR + Shift Carry Propagation (Optimal)
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 {
public:
int getSum(int a, int b) {
while (b != 0) {
int carry = (unsigned int)(a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
max_int = 0x7FFFFFFF
while b != 0:
carry = ((a & b) << 1) & mask
a = (a ^ b) & mask
b = carry
return a if a <= max_int else ~(a ^ mask)function getSum(a, b) {
while (b !== 0) {
const carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}Edge Cases to Watch
- One or both inputs are zero (returns the other integer immediately)
- One integer is negative and one is positive (subtraction is naturally handled by two's complement)
- Opposite numbers with the same magnitude (e.g. 5 and -5 sum to 0)
- Large values near 32-bit INT_MAX or INT_MIN
Master the Bit Manipulation Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Bit Manipulation pattern.
How to Recognize This Pattern
- "Add without + or -"
- XOR = addition without carry; AND<<1 = carry bits
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(1)