Sum of Two Integers
MediumBit manipulation
Given two integers a and b, return their sum.
The challenge is to do it without the + and - operators, using bitwise operators instead. The tests can only check the answers, so holding to that is up to you.
Examples
Input: a = 7, b = 5 Output: 12
0111 and 0101 share bits 0 and 2, so those carry, and the sum is 1100, which is 12.
Input: a = -4, b = 10 Output: 6
Negative numbers work too: -4 plus 10 is 6.
Constraints
-1000 ≤ a, b ≤ 1000
Stuck?
Hint 1
a ^ b adds the bits without carrying, and (a & b) << 1 is exactly the carry.
Hint 2
Adding the carry can make a new carry, so repeat: set a to the sum without carry and b to the carry until b is 0. Negative numbers work too, since the operators use 32-bit two’s complement.
The idea
Binary addition splits into two parts: a ^ b adds each column without carrying, and (a & b) << 1 is the carry, moved one column left. Adding the carry back in is another addition of the same kind, so repeat until there is no carry left.
Time O(1): at most 32 roundsExtra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
b holds what is still to be added. Once it is 0, a is the sum.
function getSum(a, b) { while (b !== 0) { const carry = (a & b) << 1; a ^= b; b = carry; } return a;}The trap
It does one round: the sum without carries, combined with the carry by |. That is right only where the carry lands on a 0. Where it lands on a 1, that column needs to carry again, and the bit is lost. Numbers whose carries never land on another 1 come out right.
function getSum(a, b) { return (a ^ b) | ((a & b) << 1); // one round: adding the carry can carry again}