371. Sum of Two Integers 🔥

Medium

Problem:

Find the sum of two integers, a and b. You cannot use the + or - operators.

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

https://leetcode.com/problems/sum-of-two-integers/

What to learn:

Implementation of Full Adder in Python

MASK acts as a bit mask, facilitating the creation of two's complement for handling negative numbers. Here, we assume the input value is a 32-bit integer with all its bits set to 1, so MASK is set to 0xFFFFFFFF.

• If it exceeds the maximum 32 bits, the masking operation removes the exceeding value.

• For negative numbers, since the Most Significant Bit (MSB) is 1, XOR it with the masking value and then apply NOT to revert it to a negative number.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        INT_MAX = 0x7FFFFFFF

        a_bin = bin(a & MASK)[2:].zfill(32)
        b_bin = bin(b & MASK)[2:].zfill(32)

        result = []
        carry = 0
        sum = 0
        for i in range(32):
            A = int(a_bin[31 -i])
            B = int(b_bin[31 -i])

            # Full Adder
            Q1 = A & B
            Q2 = A^ B
            Q3 = Q2 & carry
            sum = carry ^ Q2
            carry Q1 | Q3

            result.append(str(sum))
        if carry == 1:
            result.append('1')
        
        # Exceeded bits
        result = int(''.join(result[::-1]), 2) & MASK
        # Negative numbers
        if result > INT_MAX:
            result = ~(result ^ MASK)
        
        return result

Solution:

Simpler Full Adder

This loop continues until there is no carry left (i.e., b == 0). Each iteration, a becomes the sum without considering the carry, and b becomes the carry. The carry is then added in the subsequent iteration. The & MASK part ensures that we are only considering the least significant 32 bits of both a and b.

• a: It holds the sum of a and b without considering the carry value.

• b: It holds the carry value as the bits are advanced.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        INT_MAX = 0x7FFFFFFF

        while b != 0:
            a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
        
        # Negative numbers
        if a > INT_MAX:
            a = ~(a ^ MASK)
        
        return a

Java integer is a number of 32 bits

class Solution {
     public int getSum(int a, int b) {
        while (b != 0) {
            int tmp = (a & b) << 1;
            a = a ^ b;
            b = tmp;
        }
        return a;
    }      
}

Reference: https://www.youtube.com/watch?v=gVUrDV4tZfY