Sum of Two Integers
Last Updated: March 20, 2026
Understanding the Problem
At first glance, this seems impossible. How do you add two numbers without addition or subtraction? The answer lies in how computers actually perform addition at the hardware level: using bitwise operations.
When you add two binary digits, two things happen. You get a sum bit (which is XOR) and a carry bit (which is AND, shifted left). A CPU's adder circuit does exactly this, repeatedly, until there's no carry left. Our job is to replicate that logic in code.
The real insight here is that addition is fundamentally a bitwise operation. The + operator is just a convenient abstraction over XOR and AND.
Key Constraints:
-1000 <= a, b <= 1000→ The values are small, so even an O(n) approach where n = |a| or |b| would work. But we should aim for O(1) since this is a bit manipulation problem.- The problem explicitly bans
+and-→ We must use bitwise operators (AND, OR, XOR, shift, NOT).
Approach 1: Successive Increment/Decrement
Intuition
The simplest way to think about this: if you can't add directly, just count up (or down) one at a time. To compute a + b, start at a and move b steps in the right direction. Each step uses bitwise tricks to increment or decrement by 1 without using + or -.
How do you increment by 1 without +? Think about what happens in binary when you add 1. You flip the lowest 0-bit to 1 and clear everything below it. The expression -~x achieves this (negating the bitwise complement), which is equivalent to x + 1 without using +. Similarly, ~-x gives x - 1.
This isn't a practical solution, but it establishes a baseline and shows we can manipulate numbers without arithmetic operators.
Algorithm
- If
bis positive, incrementaby 1 exactlybtimes (using-~ato increment). - If
bis negative, decrementaby 1 exactly|b|times (using~-ato decrement). - If
bis zero, returnadirectly. - Return the final value of
a.
Example Walkthrough
Code
- Time Complexity: O(|b|). We loop exactly |b| times, performing constant-time bitwise operations in each iteration.
- Space Complexity: O(1). Only two variables are used regardless of input size.
This approach works but is painfully slow for large values of b. We're processing one unit at a time instead of handling all bit positions simultaneously. What if we could process all 32 bits in parallel, the way a real CPU adder does?
Approach 2: Bit Manipulation (XOR + AND + Shift)
Intuition
Let's go back to basics. How does binary addition actually work?
When you add two single bits:
0 + 0 = 0(no sum, no carry)0 + 1 = 1(sum = 1, no carry)1 + 0 = 1(sum = 1, no carry)1 + 1 = 10(sum = 0, carry = 1)
Look at the "sum" column: it's exactly XOR. And the "carry" column: it's exactly AND. The carry needs to be added to the next higher bit position, so we shift it left by 1.
So for two numbers a and b:
a XOR bgives us the sum of all bit positions where there's no carry.(a AND b) << 1gives us all the carries, shifted to their correct positions.
But wait, we still need to "add" the partial sum and the carry together. We can't use +, but we can apply the same XOR/AND trick again. And again. And again, until the carry becomes zero.
This is exactly how a ripple-carry adder works in hardware. Each iteration propagates carries one position further. Since integers are 32 bits wide, we'll never need more than 32 iterations.
This mirrors exactly how a full adder circuit works in a CPU. At every bit position, XOR computes the local sum and AND detects where a carry is generated. The left shift moves each carry to the next higher position where it needs to be added. By looping, we handle carries that cascade (like adding 111 + 001 where the carry ripples through all positions).
The key guarantee is that in each iteration, the carry b has strictly fewer set bits, or the set bits move to higher positions. Since we're working with fixed-width integers (32 bits), the carry must eventually become 0. In the worst case, this takes 32 iterations, one for each bit position.
Algorithm
- While
b(the carry) is not zero: - Compute the carry:
carry = (a AND b) << 1 - Compute the partial sum without carry:
a = a XOR b - Set
b = carryfor the next iteration - When
bbecomes 0, all carries have been resolved. Returna.
Example Walkthrough
Code
- Time Complexity: O(1). The loop runs at most 32 times (for 32-bit integers). Each iteration does constant-time bitwise operations. This is bounded and independent of input values.
- Space Complexity: O(1). Only a constant number of variables are used.