This is the question of the day for LeetCode 2021-9-26: “371. Sum of two integers”

1. Topic description

Given two integers A and b, without using the operators + and -, compute and return the sum of the two integers.

Example:

Input: A = 1, b = 2 Output: 3Copy the code

2. Answer

There are only four cases of addition in bitwise operations:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0(carry1)Copy the code

We can conclude that, for a and b, the addition of carry is equal to a^b.

For example, for a=2, b=3:

a = 0010
b = 0011

a ^ b:

0 0 1 0
0 0 1 1
-------
0 0 0 1
Copy the code

In a bit operation, the carry can have and obtain:

a = 0010
b = 0011

a & b:

0 0 1 0
0 0 1 1
-------
0 0 1 0
Copy the code

The resulting 0010 is not a true carry, the carry 1 needs to be one place higher, so move one place to the left to get 0100.

Then add the addition without regard to carry to get the result:

0 0 0 1
0 1 0 0
-------
0 1 0 1       (5)
Copy the code

If there is a carry after the addition, continue with the result of a^b and the carry until there are no carries.

To summarize, for a given a and b:

  • Addition without consideration of carry:a^b
  • Carry:(a & b) << 1

The carry is repeated over and over again until the carry is zero.

Easy to write the following code.

1. The iteration

const getSum = (a, b) = > {
    while (b) {
        / / carry
        const c = (a & b) << 1;
        // Do not consider the addition of carry
        a ^= b;
        // Assign the carry value to b
        b = c;
    }
    return a;
};
Copy the code

2. Recursively

It can also be implemented recursively:

const getSum = (a, b) = > {
    if(! b)return a;
    return getSum(a ^ b, (a & b) << 1);
};
Copy the code

Something simple can also be done:

const getSum = (a, b) = > (b ? getSum(a ^ b, (a & b) << 1) : a);
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”