Learning Journal

3/5/2024

Sum of Two Integers

Tags: algorithms leetcode bit_manipulation

function getSum(a: number, b: number): number {
   let result = a ^ b,
        carry = (a&b) << 1;

    while(carry !== 0) {
        const nextCarry = (result & carry) << 1;
        result ^= carry;
        carry = nextCarry;
    }

    return result;
}
function getSum(a: number, b: number): number {
   let result = a ^ b,
        carry = (a&b) << 1;

    while(carry !== 0) {
        const nextCarry = (result & carry) << 1;
        result ^= carry;
        carry = nextCarry;
    }

    return result;
}

THE PROBLEM

We can solve this problem by using bit manipulation. So, in bit level, when you add 1 and 0 or 0 and 1, you want the result to be 1; when you add 1 and 1 or 0 and 0, you want the result to be 0. That is the xor operation. However, you need to take care of the carry too. So, if two operands are 0 and 0, or 1 and 0, or 0 and 1, you want the carry to be 0. If two operands are 1 and 1, you want the carry to be 1. One more thing, you need to shift the carry by 1 unit to the left. Then, you add the carry to the result. What if that adding operation also has a carry? You continue to add it to the result until the carry equals to 0.

Revised by ChatGPT

This problem can be solved using bit manipulation, which allows us to add two numbers without using the + operator. The key idea is to use XOR and AND operations to simulate the addition process:

XOR Operation (^): In binary addition, if we ignore the carry, 1 + 0 or 0 + 1 results in 1, and 1 + 1 or 0 + 0 results in 0. This is exactly what the XOR operation does. Therefore, we can use a^b to get the sum without considering the carry.
AND Operation(&) and Left Shift(<<): The carry in binary addition occurs when both bits are 1 (i.e., 1 + 1). The AND operation can be used to find the carry bits (a + b). Since the carry needs to be added to the next higher bit, we left shift the carry by one position ((a&b) <<1).
Adding the Carry: The initial carry is calculated as described above. We then enter a loop where we continuously add the carry to the result (using XOR) and calculate the new carry. This process is repeated until there is no carry left (i.e. carry === 0).

In each iteration:

The result is updated to the XOR of the current result and the carry (result ^=carry), which adds the carry to the result.
The new carry is calculated as the AND of the current result and the carry, left-shifted by one ((result & carry) << 1).

The loop ensures that all carries are added to the result. When the carry becomes 0, the addition is complete, and the result contains the sum of the two integers.