Sum of Two Integers
Understanding the Problem
Adding two numbers without + or - comes down to how computers perform addition at the hardware level: with bitwise operations.
When you add two binary digits, you produce a sum bit (XOR) and a carry bit (AND, shifted left). A CPU's adder circuit repeats this until no carry remains. The task is to replicate that logic in code. Addition is a bitwise operation underneath, and the + operator is an abstraction over XOR and AND.
Key Constraints:
-1000 <= a, b <= 1000→ Values fit comfortably in a 32-bit signed integer, and the result range (-2000to2000) never overflows. This rules out worrying about the result, but the carry shifts still touch the sign bit, which matters for the language details below.- The problem bans
+and-→ The only arithmetic available is bitwise: AND, OR, XOR, shift, NOT.
Approach 1: Successive Increment/Decrement
Intuition
If you can't add directly, count up or down one step at a time. To compute a + b, start at a and move b steps toward the result. Each step increments or decrements by 1 using only bitwise operators.
A single increment without + comes from the identity -~x == x + 1. The bitwise complement ~x equals -x - 1 in two's complement, so negating it gives x + 1. By the same reasoning, ~-x == x - 1.
This is slow, but it establishes a baseline and shows that arithmetic can be expressed entirely with bitwise 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.
Processing one unit at a time is slow when b is large. The next approach handles all 32 bit positions at once, the way a CPU adder does, which brings the running time down to a fixed number of iterations.
Approach 2: Bit Manipulation (XOR + AND + Shift)
Intuition
Binary addition of two single bits has two outputs, a sum and a carry:
0 + 0 = 0(sum = 0, carry = 0)0 + 1 = 1(sum = 1, carry = 0)1 + 0 = 1(sum = 1, carry = 0)1 + 1 = 10(sum = 0, carry = 1)
The sum column is XOR, and the carry column is AND. A carry belongs in the next higher bit position, so it is shifted left by 1.
Applied to two full numbers a and b:
a XOR bgives the sum at every bit position, ignoring carries.(a AND b) << 1gives the carries, shifted into the positions they affect.
The partial sum and the carry still need to be combined, and that combination is itself an addition. Applying the same XOR and AND-shift step to them, repeatedly, resolves it. This is how a ripple-carry adder works in hardware: each iteration moves carries one position further. With 32-bit integers, the carry runs out of room after at most 32 iterations.
Every iteration shifts the carry left by one position. The lowest set bit of the carry therefore moves strictly higher each time, so within 32 iterations the carry has nowhere left to go and becomes 0. Cascading carries, such as adding 111 + 001, take more iterations because each carry generates the next, but the leftward shift still bounds the total at the integer width.
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.