Sum of Two Integers

Medium Bit Manipulation Basics Original on LeetCode

Reported atSwiggy

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 combine a and b.

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.

00:00
Testcase

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.

ApproachTimeSpace
Bit-by-bit full adderO(1)O(1)
Optimal (XOR plus carry loop)O(1)O(1)

1Bit-by-bit full adder

TimeO(1)Always exactly 32 iterations.
SpaceO(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.

  1. Set result = 0 and carry = 0.
  2. For i from 0 to 31: x = bit i of a, y = bit i of b.
  3. sum bit = x ^ y ^ carry; carry = (x & y) | (x & carry) | (y & carry).
  4. 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;
    }
}

2Optimal (XOR plus carry loop)

TimeO(1)At most 32 rounds, since the carry moves left every round.
SpaceO(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.

  1. While b != 0: carry = (a & b) << 1; a = a ^ b; b = carry.
  2. Return a.
  3. 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;
    }
}

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.