Return the sum of two integers a and b. You may not use the plus or minus operators.
DSA Animator › DSA Revision › Bit Manipulation › Sum of Two Integers
Remember: XOR is sum without carry, AND shifted is the carry. Repeat until the carry is zero. The video solves Sum of Two Integers (LeetCode 371, Medium) with the XOR + Carry pattern from the Bit Manipulation topic, and you can replay every step in the interactive Sum of Two Integers animation.
Return the sum of two integers a and b. You may not use the plus or minus operators.
For a equal to 5 and b equal to 3, the answer is 8.
Adding one at a time with increments is not allowed either, and it would be slow. We can rebuild addition from bit operations, just like a circuit does.
XOR adds two bits without the carry: 1 plus 1 gives 0. AND finds where both bits are 1, which is where a carry is produced. Shift those carries left by one, because a carry moves into the next column. Repeat with the partial sum and the carries, until no carry is left.
5 is 0101 and 3 is 0011. XOR gives 0110, which is 6, and the carry is 0001 shifted, which is 0010. 6 XOR 2 is 0100, and the carry is 0010 shifted, which is 0100. 4 XOR 4 is 0, and the carry is 1000. 0 XOR 8 is 8, and now the carry is 0. So the sum is 8.
In code, loop while b is not 0. Compute carry as a AND b, shifted left by one. Set a to a XOR b, and b to the carry. Return a, so it's O of the number of bits.
Remember: XOR is sum without carry, AND shifted is the carry. Repeat until the carry is zero.