💬 Discord
Sign In
NeetCode #863LC-371MediumBit ManipulationBlind 75NC 150NC 250
← Back to All Problems

#863 · #371 · Sum of Two Integers(两整数之和)

📌 Problem Statement & Constraints

Given two integers a and b, return their sum without using the operators + and -. Constraints: -1000 <= a, b <= 1000.

💡 Core Algorithmic Approaches

  1. Split the addition into two independent parts: a ^ b is the sum ignoring carries, and (a & b) << 1 is the carry pattern.
  2. Repeat the process with the carry as the new second operand until the carry becomes zero.
  3. In Python the integers are unbounded, so negative values have infinitely many leading ones and the loop never terminates without a mask.
  4. Mask every intermediate value to 32 bits, then convert a negative two's-complement pattern back with ~(a ^ mask).

💻 Benchmark Python3 Implementation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF               # simulate 32-bit two's complement
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        return a if a < 0x80000000 else ~(a ^ mask)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): at most 32 carry-propagation iterations.
💾 Space Complexity
O(1): two integers.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the 32-bit mask: Python's unbounded integers make the carry loop run forever for negative operands.
  • Returning the raw accumulator: if the true sum is negative, a holds an unsigned 32-bit pattern; convert with ~(a ^ mask).
  • Using recursion: the loop is clearer and avoids stack-depth concerns.
  • Masking only a and not the carry: both the sum and the carry must stay inside 32 bits, otherwise the sign bit leaks upward.