371. Sum of Two Integers – Leetcode Solutions

Description

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

Examples:

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Solution in Python

To find the sum of two integers a and b without using the + and - operators, we can use bitwise operations. Specifically, we can use bitwise XOR (^) and AND (&) operations to mimic the process of addition.

Key Concepts:

1. Bitwise XOR (^):
   • The XOR of two bits gives the addition without carrying. For example, 1 ^ 1 = 0, 1 ^ 0 = 1, and 0 ^ 0 = 0.
   • XOR between two numbers will give us the sum of the numbers but without considering any carry-over values.
2. Bitwise AND (&):
   • The AND operation can help us find the carry bits. For example, 1 & 1 = 1, 1 & 0 = 0, and 0 & 0 = 0.
   • Shifting the carry left by one position (<< 1) will move the carry to the correct position where it should be added in the next iteration.
3. 32-bit Mask:
   • Since Python integers are not fixed-width, we simulate a 32-bit integer by using a mask of 0xFFFFFFFF.
   • This mask helps handle negative numbers and ensures our calculations stay within a 32-bit signed integer range.
4. Two’s Complement for Negative Numbers:
   • If the final result exceeds the range of 32-bit signed integers, we adjust the result to fit within this range by converting it using two’s complement representation.

Algorithm:

1. Loop until there is no carry:
   • Calculate the XOR of a and b to get the sum without carrying.
   • Calculate the carry by AND-ing a and b and shifting it left by 1.
   • Update a to be the new sum and b to be the new carry.
2. Final Adjustments for 32-bit Results:
   • If the result a is larger than the maximum 32-bit signed integer (0x7FFFFFFF), adjust a to fit within 32-bit signed integers by applying a mask and two’s complement.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Mask to get last 32 bits (to simulate 32-bit integer operations)
        mask = 0xFFFFFFFF
        
        while b != 0:
            # XOR to get addition result without carry
            sum_without_carry = (a ^ b) & mask
            # AND and shift to get the carry bits
            carry = ((a & b) << 1) & mask
            # Update a and b for the next iteration
            a, b = sum_without_carry, carry
        
        # If a is greater than 0x7FFFFFFF, it means a is negative in 32-bit context
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

Explanation of the Code:

1. Looping with XOR and AND:
   • In each iteration, a is updated to the sum without carry, and b is updated to the carry. This loop continues until there is no carry (b == 0).
2. Two’s Complement Adjustment:
   • If a exceeds 0x7FFFFFFF (the maximum positive value in a 32-bit signed integer), it means a is representing a negative number in 32-bit. We convert it by taking the two’s complement using ~(a ^ mask).

Solution in C++

class Solution {
public:
    int getSum(int a, int b) {
        // Loop until there is no carry
        while (b != 0) {
            // Calculate the carry, which is common set bits of a and b
            int carry = (a & b) << 1;

            // Sum of bits where at least one of the bits is not set (XOR)
            a = a ^ b;

            // Carry is added to the result in the next iteration
            b = carry;
        }
        
        // a contains the result, return it
        return a;
    }
};

Solution in Javascript

var getSum = function(a, b) {
    // We will iterate until there are no carry bits left
    while (b !== 0) {
        // `carry` will hold the common set bits of a and b
        let carry = a & b;
        
        // Sum of bits of a and b where at least one of the bits is not set
        a = a ^ b;
        
        // Shift carry by one so that adding it to `a` gives the correct sum
        b = carry << 1;
    }
    
    // When b becomes 0, `a` contains the result
    return a;
};

Solution in Java

class Solution {
    public int getSum(int a, int b) {
        // Loop until there is no carry left
        while (b != 0) {
            // Calculate carry where both bits are 1
            int carry = a & b;

            // Perform the addition without carry using XOR
            a = a ^ b;

            // Shift carry to the left by one to add it in the next position
            b = carry << 1;
        }
        
        // Return the final result stored in 'a' when no carry remains
        return a;
    }
}