leetcode/en/lcci/17.1/

[giscus[bot]]

leetcode/en/lcci/17.1/

LeetCode solutions in any programming language

https://doocs.github.io/leetcode/en/lcci/17.1/

[rajputanisha]

class Solution {
public:
int getSum(int a, int b) {

    while(b != 0){
      int   sum = a^b;
      int   c = (a&b)<<1;
       a = sum;
         b = c;           
    }
   
    return a ;
}

};

Why use XOR and AND operations for addition?
The goal is to add two numbers without using the + or - operators. So, we need to simulate the binary addition process, and that’s where the XOR and AND operations come in.

Intuition behind XOR:
XOR (exclusive OR) gives us the sum without carrying.
When we add two bits:
0 + 0 = 0
1 + 0 = 1 (or 0 + 1 = 1)
1 + 1 = 0 but carry 1 to the next bit.
XOR acts like this:
0 ^ 0 = 0 → no carry.
1 ^ 0 = 1 → sum without carry.
1 ^ 1 = 0 → no sum but needs carry to next bit.
Intuition behind AND and shift operation:
After XOR, we need to account for the carry that might be generated when both bits are 1.
When both bits are 1, we need to carry 1 to the next bit.
This is where AND helps us find where the carry is.
1 AND 1 = 1 (we need to carry 1 to the next bit).
1 AND 0 = 0 or 0 AND 1 = 0 → no carry.
After finding the carry, we shift it left by 1 because the carry moves to the next higher bit position.
Example:
Let's walk through an example with two numbers:

a = 14 (which is 1110 in binary).
b = 4 (which is 0100 in binary).
Step-by-step:
First step (XOR and AND):

a = 14 (1110), b = 4 (0100).
XOR: a ^ b = 1110 ^ 0100 = 1010 (This is the sum without carry).
AND: (a & b) << 1 = (1110 & 0100) << 1 = 0100 << 1 = 1000 (This is the carry).
Now, we update a to the sum (1010 or 10) and b to the carry (1000 or 8).

Second step (XOR and AND again):

Now a = 10 (1010) and b = 8 (1000).
XOR: a ^ b = 1010 ^ 1000 = 0010 (This is the sum without carry).
AND: (a & b) << 1 = (1010 & 1000) << 1 = 1000 << 1 = 10000 (This is the carry).
Now, update a to the sum (2 or 0010) and b to the carry (16 or 10000).

Third step (XOR and AND again):

Now a = 2 (0010) and b = 16 (10000).
XOR: a ^ b = 0010 ^ 10000 = 11010 (This is the sum without carry).
AND: (a & b) << 1 = (0010 & 10000) << 1 = 0000 << 1 = 0000 (No carry).
Now, b becomes 0, and we stop the loop because there's no carry left.

Final Result:
Now, a holds the final sum (18 or 11010 in binary).

Why continue until no carry?
Carry: The carry is what you would normally "add" to the next bit in traditional addition. But we need to calculate it explicitly using the AND operation.
The XOR operation gives us the partial sum but doesn't handle the carry.
The loop continues until there’s no carry left. Once b is 0, all carries have been processed, and we have the final result.
Simple analogy:
Think of adding two numbers as two people adding coins into different piles.
They check if both piles have a coin, and if they do, they "carry" one coin to the next pile (this is the carry).
They keep doing this until there are no more piles left to carry coins to (when the carry is zero).
In short:
XOR is used to calculate the sum without the carry.
AND is used to find where the carry needs to go, and we shift it left to the next bit.
We repeat this process (using the while loop) until there is no more carry left, meaning the addition is complete.