Start learning free

LESSON 308 OF 321 · BIT MANIPULATION

Sum of Two Integers in Java: Adding with XOR and Carries

Practice O(1) Read the full explanation

You get two integers, a and b.

Return a + b. Your code may not use + or -.

 

Example 1:

Input: a = 4, b = 9
Output: 13
Explanation: In binary, this is 0100 + 1001.
No column has two 1s, so nothing carries.
The sum is 1101, which is 13.

Example 2:

Input: a = 7, b = 1
Output: 8
Explanation: In binary, this is 111 + 001.
The last column has two 1s.
It writes 0 and carries 1.
In each of the next two columns, the carry meets a 1.
Each time, it writes 0 and carries 1 again.
The sum is 1000, which is 8.

Example 3:

Input: a = -9, b = 4
Output: -5
Explanation: The computer stores negative numbers in two's complement.
Adding column by column works for them too.

 

Constraints:

  • a and b are each from -1,000 to 1,000.
Note:

Use bitwise operations instead of + and -. Your algorithm should run in O(1) time and use O(1) extra space: it may loop once for each bit of the integer type, but no more.



Add the two numbers in binary, one column at a time, as you would on paper. In a column, 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10: a 0 in that column and a 1 carried into the next one. The digit left in each column is the XOR of the two bits, and a carry appears only where both bits are 1: the AND of the two bits.

a XOR b is the sum without the carries, and (a AND b) shifted left by one place is the carries. Those two numbers still add up to a + b, so repeat with them: XOR them, compute their carries, and stop when there is no carry left.

Each round moves the carries at least one place to the left, so the loop runs at most once per bit of the integer: 32 times for a 32-bit integer. That doesn't depend on the input: O(1) time.
We keep a few numbers, so the extra space is O(1).
STEP 1 OF 5
    Ctrl + Enter to check

    JAVA · BIT MANIPULATION

    Sum Of Two Integers in Java, explained

    Problem overview

    The method getSum(int a, int b) receives two integers and returns a + b without using the operators + and -. The values range from -1000 to 1000, and negative numbers are allowed.

    With a = 1 and b = 2 the answer is 3. With a = 2 and b = 3 it is 5, and with a = -5 and b = 3 it is -2. The method has to work with bitwise operations, in O(1) time and space: it may loop once for each bit of the integer type, but no more.

    Approach: add column by column, as on paper

    Adding two binary numbers on paper goes column by column. In one column, 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10: a 0 stays in that column and a 1 is carried into the next column on the left.

    Two bitwise operations capture this:

    • a ^ b (XOR) gives the digit left in each column, because 1 + 1 leaves 0 and the other cases leave the sum itself. It is the sum with all carries left out.
    • (a & b) << 1 gives the carries. A carry appears only in a column where both bits are 1, which is a & b, and it lands one column to the left, which is the shift.

    These two numbers still add up to a + b, so the problem has the same shape with different numbers: add the partial sum and the carries. Repeat, until no carries are left. The partial sum is then the answer.

    The loop terminates because each round moves the lowest carry at least one place to the left. An int has 32 bits, so after at most 32 rounds the carries have fallen off the left end and are 0. That count doesn't depend on the values, which gives O(1) time.

    For a = 2 and b = 3 the loop produces this:

    a=1 b=4
    a=5 b=0
    

    The first round turns 2 (010) and 3 (011) into the carry-free sum 1 and a carry of 4, and the second round adds those with no carry left. The result is 5.

    Step by step

    1. Loop while b != 0. Here a holds the sum so far and b the carries still to be added.
    2. Compute the carries in an int named carry: (a & b) << 1.
    3. Set a to a ^ b, the sum without the carries.
    4. Set b to carry so the next round adds them. The value a + b stays the same from round to round: part of it just moves from one number to the other.
    5. Return a. With no carries left, the whole sum is in a.

    The solution in Java

    class Solution {
        public int getSum(int a, int b) {
            while (b != 0) {
                int carry = (a & b) << 1;
                a = a ^ b;
                b = carry;
            }
            return a;
        }
    }
    

    The Java details worth a closer look:

    • Negative numbers need nothing special. Java stores an int in two's complement, and this column-by-column addition is the same one the processor performs. For a = -5 and b = 3 the loop goes through two rounds, a=-8 b=6 and then a=-2 b=0, and returns -2.
    • The carry loop ends. The shift << 1 discards the bit that leaves the 32-bit int, so carries can't circulate forever.
    • Overflow wraps silently. If the true sum doesn't fit in an int, the result wraps around, as with +: getSum(Integer.MAX_VALUE, 1) returns -2147483648. The lesson's values are small, so this can't happen there.
    • Parameters are copies. Assigning to a and b changes only the method's own variables.
    • Save the carry before changing a. a & b needs the original a. Once a has become a ^ b, the carries can no longer be computed, which is why carry is computed first.

    Complexity

    Time: O(1). Each round pushes the lowest carry at least one place to the left, so the loop runs at most 32 times for an int, whatever the values are.

    Space: O(1). The method keeps a, b and carry.

    Edge cases and common mistakes

    • Two zeros. b is 0 from the start, so the loop never runs and the method returns 0.
    • Opposite numbers. getSum(7, -7) and getSum(-1, 1) both return 0. The carry travels left until it falls off the end of the 32 bits, which can take up to 32 rounds.
    • Equal numbers. getSum(5, 5) returns 10: every column with a 1 produces a carry, and the next round adds them with none left over.
    • Overwriting a too early. Computing a = a ^ b before the carry loses the information the carry needs.
    • Forgetting the shift. Using a & b without << 1 puts each carry in the column that produced it instead of the next one, and the result is wrong.
    • Looping on a. The loop must run while the carries b are non-zero, not a.

    Testing

    • a = 1, b = 2 gives 3.
    • a = 2, b = 3 gives 5.
    • a = -5, b = 3 gives -2.
    • a = 0, b = 0 gives 0.
    • a = 7, b = -7 gives 0.
    • a = 1000, b = -1000 gives 0.
    • a = 5, b = 5 gives 10.
    Keep going with Java1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free