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 ^ bis 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
- Loop while
b !== 0. Hereais the sum so far andbthe carries still to add. - Compute
carrywithlet:(a & b) << 1, the bits set in both numbers, moved one column left. - Set
atoa ^ b, the sum without carries. - Set
btocarry. Carry has to be saved beforeachanges, since computing it needs the olda. - Return
aonce 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-5is11111111111111111111111111111011. 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
bis 0. That is theO(1)bound. - Results stay in the 32-bit range. Because
^returns a 32-bit integer,getSum(2147483647, 1)returns-2147483648, where the ordinary2147483647 + 1gives2147483648. This is outside the lesson's range of -1000 to 1000. letinside the loop.carryis created anew each round, which is fine. The parametersaandbare 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)returns0, and the loop never runs. - Opposite numbers.
getSum(7, -7)andgetSum(-1, 1)return0. The carry travels all the way out of the 32 bits. - Both negative.
getSum(-1000, -1000)returns-2000. - Mixed signs.
getSum(5, -3)returns2. - Forgetting the shift.
a & bmarks the columns that produce a carry, but the carry has to be added to the next column. Without<< 1the sum is wrong. - Overwriting
abefore computing the carry. If you seta = a ^ bfirst,a & buses 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 = 2gives3.a = 2,b = 3gives5.a = -5,b = 3gives-2.a = 0,b = 0gives0.a = -1,b = 1gives0.a = 1000,b = 1000gives2000.a = -1000,b = -1000gives-2000.a = 5,b = -3gives2.
