LeetCode //C - 371. Sum of Two Integers

371. Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Example 2:

Constraints:

-1000 <= a, b <= 1000

From: LeetCode
Link: 371. Sum of Two Integers

Solution:

Ideas:

1. XOR (^) for Sum Without Carry

The XOR operation a ^ b computes the sum of a and b without considering the carry.
For each bit position, XOR produces a 1 if the bits are different and a 0 if they are the same.
This is equivalent to binary addition without carrying over (e.g., 1 ^ 1 is 0, similar to how 1 + 1 without carry is 0).

2. AND (&) and Shift for Carry

The AND operation a & b computes the carry for each bit position.
It produces a 1 only where both bits of a and b are 1.
This carry needs to be added to the next higher bit, so we left-shift it by one position using << 1.

3. Iterating Until No Carry

The process is repeated:
Calculate the carry.
Update a to be the sum without the carry.
Update b to be the carry shifted left by one bit.
This continues until there is no carry left (b becomes 0).

4. Masking to 32 Bits

To handle potential overflow and to manage negative numbers in a 32-bit integer system, we mask the results to 32 bits using & 0xFFFFFFFF.
This ensures that the intermediate results remain within the range of a 32-bit signed integer.

Code:

int getSum(int a, int b) {
    while (b != 0) {
        // Calculate carry and mask it to 32 bits
        unsigned int carry = (unsigned int)(a & b) & 0xFFFFFFFF;
        // Sum without carry and mask it to 32 bits
        a = (a ^ b) & 0xFFFFFFFF;
        // Shift carry to the left by 1 and mask it to 32 bits
        b = (carry << 1) & 0xFFFFFFFF;
    }
    // Return the result as a signed 32-bit integer
    return a;
}

Navigator_Z