LeetCode 371 - Sum of Two Integers

This Medium problem asks to compute the sum of two integers a and b without using the arithmetic operators + and -. I implemented software-level full adder logic using bitwise XOR for addition without carry, AND for carry calculation, and 32-bit masking to handle Python’s arbitrary-precision integer representations.

---

Problem link and explanation

• Problem: 371. Sum of Two Integers
• Summary: Return the sum of two integers a and b without using the + and - operators.

In hardware circuits, binary addition calculates the sum bit via XOR (^) and the carry bit via AND (&). In Python, integers do not overflow automatically at 32 bits, requiring explicit masks (0xFFFFFFFF) to emulate two’s complement behavior for negative results.

---

Approach

Define a 32-bit bitmask mask = 0xFFFFFFFF and maximum positive 32-bit boundary max_int = 0x7FFFFFFF.

mask = 0xFFFFFFFF
max_int = 0x7FFFFFFF

while b != 0:
    carry = (a & b) << 1
    a = (a ^ b) & mask
    b = carry & mask

return a if a <= max_int else ~(a ^ mask)

1. Calculate carry: Compute (a & b) << 1 to identify all bit positions generating a carry and shift them one position to the left.
2. Add without carry: Compute (a ^ b) & mask to perform partial sum addition across all bit columns.
3. Loop: Repeat until no carry remains (b == 0).
4. Sign restoration: If a <= max_int, return a as a positive integer. If a > max_int, convert the 32-bit two’s complement representation back to Python’s negative format using ~(a ^ mask).

---

Complexity analysis

• Time complexity: O(1)
  • For 32-bit integers, carries propagate at most 32 times, bounding loop iterations to a constant upper limit.
• Space complexity: O(1)
  • Operates with only a few integer variables and bitwise mask constants.

---

Implementation code

class Solution:

    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        max_int = 0x7FFFFFFF

        while b != 0:
            carry = (a & b) << 1
            a = (a ^ b) & mask
            b = carry & mask

        return a if a <= max_int else ~(a ^ mask)

---

Summary and reflection

Implementing arithmetic operations with bitwise primitives mirrors logic gates inside hardware arithmetic logic units (ALUs). In Python, handling arbitrary-precision integer expansion via 32-bit masking and explicit two’s complement sign conversion is the essential prerequisite for bitwise addition.