Start learning free

LESSON 592 OF 671 · BIT MANIPULATION

Sum of Two Integers in JavaScript: Add with XOR and 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

    JAVASCRIPT · BIT MANIPULATION

    Sum Of Two Integers in JavaScript, explained

    Problem overview

    The method getSum(a, b) receives two integers and returns their sum, a + b, without using the operators + and -. Bitwise operators are allowed. With a = 2 and b = 3 the answer is 5, and with a = -5 and b = 3 it is -2. The values lie between -1000 and 1000.

    The statement asks for O(1) time and O(1) extra space: the loop may run once per bit of the integer type, but no more.

    Approach: add column by column, like on paper

    Adding in binary works one column at a time. In a column, 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10: a 0 stays in that column and a 1 is carried to the next one on the left.

    • The digit left in each column is the XOR of the two bits: a ^ b is the sum with the carries left out.
    • A carry appears only where both bits are 1: a & b. It belongs one column to the left, so the carries are (a & b) << 1.

    These two numbers still add up to a + b. So replace a with the partial sum, b with the carries, and repeat. Each round, the carries move at least one place to the left. Once there are no carries left, b is 0 and a holds the whole sum.

    For a = 2 and b = 3, each line shows a and b after a round:

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

    The first round: 2 ^ 3 is 1 (01) and (2 & 3) << 1 is 4 (100). The second round has no common 1 bits, so there is no carry, and 1 ^ 4 gives 5.

    Negative numbers work with the same loop. For a = -5 and b = 3:

    a = -8, b = 6
    a = -2, b = 0
    

    Step by step

    1. Loop while b !== 0. Here a is the sum so far and b the carries still to add.
    2. Compute carry with let: (a & b) << 1, the bits set in both numbers, moved one column left.
    3. Set a to a ^ b, the sum without carries.
    4. Set b to carry. Carry has to be saved before a changes, since computing it needs the old a.
    5. Return a once no carries remain.

    The solution in JavaScript

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

    JavaScript details that matter:

    • Bitwise operators use 32-bit signed integers. &, ^ and << convert their operands to 32-bit integers in two's complement, where -5 is 11111111111111111111111111111011. That is why negative numbers need no special code. The addition circuit in a processor works the same way.
    • The loop always ends. A carry moves at least one place left each round, and a 32-bit value has only 32 places, so after at most 32 rounds the carry falls off the left end and b is 0. That is the O(1) bound.
    • Results stay in the 32-bit range. Because ^ returns a 32-bit integer, getSum(2147483647, 1) returns -2147483648, where the ordinary 2147483647 + 1 gives 2147483648. This is outside the lesson's range of -1000 to 1000.
    • let inside the loop. carry is created anew each round, which is fine. The parameters a and b are reassigned directly.
    • Use !== to compare with 0. It is a strict comparison, with no type conversion.

    Complexity

    Time: O(1). The loop runs at most 32 times, whatever the inputs, because the carries move left every round and drop out after the 32nd place.

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

    Edge cases and common mistakes

    • Zeros. getSum(0, 0) returns 0, and the loop never runs.
    • Opposite numbers. getSum(7, -7) and getSum(-1, 1) return 0. The carry travels all the way out of the 32 bits.
    • Both negative. getSum(-1000, -1000) returns -2000.
    • Mixed signs. getSum(5, -3) returns 2.
    • Forgetting the shift. a & b marks the columns that produce a carry, but the carry has to be added to the next column. Without << 1 the sum is wrong.
    • Overwriting a before computing the carry. If you set a = a ^ b first, a & b uses the changed value. Compute the carry first.
    • Using - to negate. The statement forbids it, and it isn't needed: two's complement handles negatives.

    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 = -1, b = 1 gives 0.
    • a = 1000, b = 1000 gives 2000.
    • a = -1000, b = -1000 gives -2000.
    • a = 5, b = -3 gives 2.
    Keep going with JavaScript650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free