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) << 1gives the carries. A carry appears only in a column where both bits are 1, which isa & 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
- Loop while
b != 0. Hereaholds the sum so far andbthe carries still to be added. - Compute the carries in an
intnamedcarry:(a & b) << 1. - Set
atoa ^ b, the sum without the carries. - Set
btocarryso the next round adds them. The valuea + bstays the same from round to round: part of it just moves from one number to the other. - Return
a. With no carries left, the whole sum is ina.
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
intin two's complement, and this column-by-column addition is the same one the processor performs. Fora = -5andb = 3the loop goes through two rounds,a=-8 b=6and thena=-2 b=0, and returns -2. - The carry loop ends. The shift
<< 1discards the bit that leaves the 32-bitint, 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
aandbchanges only the method's own variables. - Save the carry before changing
a.a & bneeds the originala. Onceahas becomea ^ b, the carries can no longer be computed, which is whycarryis 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.
bis 0 from the start, so the loop never runs and the method returns 0. - Opposite numbers.
getSum(7, -7)andgetSum(-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
atoo early. Computinga = a ^ bbefore the carry loses the information the carry needs. - Forgetting the shift. Using
a & bwithout<< 1puts 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 carriesbare non-zero, nota.
Testing
a = 1,b = 2gives 3.a = 2,b = 3gives 5.a = -5,b = 3gives -2.a = 0,b = 0gives 0.a = 7,b = -7gives 0.a = 1000,b = -1000gives 0.a = 5,b = 5gives 10.
