LeetCode 371: Sum of Two Integers Solution in Python – A Step-by-Step Guide

What Is LeetCode 371: Sum of Two Integers?

LeetCode 371: Sum of Two Integers gives you two integers, a and b, and asks you to compute their sum without using the + or - operators. It’s a problem that tests your understanding of binary arithmetic and bitwise manipulation—turning a simple task into a clever puzzle!

Problem Statement

• Input:
• a: Integer.
• b: Integer.
• Output: Integer - Sum of a and b.
• Rules:
• Do not use + or - operators.
• Handle both positive and negative integers.

Constraints

• -1000 <= a, b <= 1000

Examples

• Input: a = 1, b = 2
• Output: 3
• 1 + 2 = 3, bitwise: 01 + 10 = 11.
• Input: a = 2, b = 3
• Output: 5
• 2 + 3 = 5, bitwise: 10 + 11 = 101.
• Input: a = -2, b = 3
• Output: 1
• -2 + 3 = 1, bitwise handling required.

These show the bitwise twist—let’s solve it!

Understanding the Problem: Adding Without Addition

To tackle LeetCode 371 in Python, we need to: 1. Compute a + b without using + or -. 2. Use bitwise operations (AND, XOR, shift) to mimic addition. 3. Handle 32-bit integer constraints and negative numbers.

A naive approach might convert to strings or use loops, but bitwise is the way. We’ll use:

• Best Solution: Bitwise operations—O(log n) time, O(1) space—fast and true to intent.
• Alternative Solution: String conversion—O(log n) time, O(log n) space—illustrative but against rules.

Let’s sum with the best solution!

Best Solution: Bitwise Operations

Why This Is the Best Solution

The bitwise operations approach runs in O(log n) time (where n is the maximum number of bits, 32 here) by simulating addition using XOR for sum without carry, AND for carry, and left shifts to propagate carry. It’s the most efficient and adheres to the problem’s spirit—purely bitwise with no arithmetic operators!

How It Works

Think of binary addition:

• XOR (^): Adds bits without carry (e.g., 1 ^ 1 = 0, 1 ^ 0 = 1).
• AND (&): Computes carry (e.g., 1 & 1 = 1, 1 & 0 = 0).
• Left Shift (<<): Moves carry to next position.
• Iterate: Repeat until no carry remains.
• Mask: Handle 32-bit signed integers in Python (mask to 32 bits, adjust for sign).

It’s like adding bits step-by-step!

Step-by-Step Example

For a = 1, b = 2:

• Binary: a = 01, b = 10.
• Step 1:
• Sum = a ^ b = 01 ^ 10 = 11 (3).
• Carry = (a & b) << 1 = (01 & 10) << 1 = 00 << 1 = 00 (0).
• Step 2: Carry = 0, stop.
• Result: 3.

For a = 2, b = 3:

• Binary: a = 10, b = 11.
• Step 1:
• Sum = 10 ^ 11 = 01 (1).
• Carry = (10 & 11) << 1 = 10 << 1 = 100 (4).
• Step 2:
• Sum = 01 ^ 100 = 101 (5).
• Carry = (01 & 100) << 1 = 0 << 1 = 0.
• Step 3: Carry = 0, stop.
• Result: 5.

For a = -2, b = 3 (32-bit signed):

• Binary: a = ~1 + 1 = 111...10, b = 000...11.
• Step 1:
• Sum = 111...10 ^ 000...11 = 111...01.
• Carry = (111...10 & 000...11) << 1 = 000...10 << 1 = 000...100.
• Step 2:
• Sum = 111...01 ^ 000...100 = 111...101.
• Carry = 0 (no overlap).
• Mask: 111...101 & 0xffffffff = 111...101 (still -3 in 32-bit, adjust later).
• Result: After masking and sign handling, 1.

Code with Explanation

Here’s the Python code using bitwise operations:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Mask to handle 32-bit integers
        mask = 0xffffffff  # 32 ones

        # Iterate until no carry
        while b & mask:
            carry = ((a & b) << 1) & mask
            a = (a ^ b) & mask
            b = carry

        # Handle negative numbers (Python's unlimited int issue)
        # If a is negative in 32-bit, adjust to signed representation
        if a >> 31 & 1:  # Check if sign bit is 1
            return ~(a ^ mask)  # Convert to negative

        return a

Explanation

• Line 4: mask: 32-bit mask (0xffffffff) to cap Python’s unlimited integers.
• Lines 6-9: Bitwise addition loop:
• While carry (b) exists within 32 bits:
• carry = (a & b) << 1: Compute carry, shift left, mask to 32 bits.
• a = a ^ b: Sum without carry, mask to 32 bits.
• b = carry: Update carry for next iteration.
• Lines 11-13: Handle negative result:
• If a’s 31st bit (sign bit) is 1, it’s negative in 32-bit.
• ~(a ^ mask): Convert to signed negative (two’s complement adjustment).
• Line 15: Return a if positive.
• Time: O(log n)—iterations proportional to bit width (max 32).
• Space: O(1)—no extra space.

This is like binary addition unplugged—pure bits!

Alternative Solution: String Conversion (Illustrative)

Why an Alternative Approach?

The string conversion solution runs in O(log n) time but uses O(log n) space and technically violates the no-arithmetic spirit by relying on string manipulation. It’s included for illustration—showing a creative workaround, though not recommended!

How It Works

• Convert: Turn a and b to binary strings.
• Add: Simulate binary addition with string operations.
• Result: Convert back to integer.

Step-by-Step Example

For a = 1, b = 2:

• Binary: a = "1", b = "10".
• Pad: a = "01", b = "10".
• Add:
• "01" + "10" → carry=0, sum="11" (bitwise string logic).
• Result: int("11", 2) = 3.

Code with Explanation

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Convert to binary strings, remove '0b' prefix
        bin_a = bin(a & 0xffffffff)[2:].zfill(32)
        bin_b = bin(b & 0xffffffff)[2:].zfill(32)

        # Binary addition without +
        carry = 0
        result = []
        for i in range(31, -1, -1):
            bit_a = int(bin_a[i])
            bit_b = int(bin_b[i])
            total = bit_a + bit_b + carry
            result.append(str(total % 2))
            carry = total // 2

        # Convert back to integer
        bin_result = ''.join(result[::-1])
        return int(bin_result, 2) if int(bin_result, 2) < 2**31 else int(bin_result, 2) - 2**32

Explanation

• Lines 4-5: Convert to 32-bit binary strings, pad to 32.
• Lines 7-14: Simulate addition:
• Iterate right-to-left, add bits with carry.
• Append total % 2, update carry.
• Lines 16-17: Join reversed bits, convert to int, adjust for signed 32-bit.
• Time: O(log n)—bit operations (32 steps).
• Space: O(log n)—string storage.

It’s a cheat using strings—not the intended bitwise path!

Comparing the Two Solutions

• Bitwise Operations (Best):
• Time: O(log n)—bitwise steps.
• Space: O(1)—no extra space.
• Pros: Fast, follows rules, elegant.
• Cons: Bitwise logic less intuitive.
• String Conversion (Alternative):
• Time: O(log n)—string ops.
• Space: O(log n)—strings.
• Pros: Visual binary process.
• Cons: Against spirit, more space.

Bitwise wins for adherence and efficiency!

Additional Examples and Edge Cases

• a=0, b=0: 0.
• a=-1, b=1: 0.
• a=1000, b=1000: 2000 (within 32-bit).

Bitwise handles all, strings work but cheat.

Complexity Breakdown

• Bitwise:
• Time: O(log n).
• Space: O(1).
• String:
• Time: O(log n).
• Space: O(log n).

Bitwise excels for space and intent.

Key Takeaways

• Bitwise: Add with bits—fast and pure!
• String: Cheat with text—clear but off-rule!
• Binary: Numbers are bits.
• Python Tip: Bit ops rock—see [Python Basics](/python/basics).

Final Thoughts: Sum Those Bits

LeetCode 371: Sum of Two Integers in Python is a bitwise challenge. Bitwise operations are the efficiency champ, while string conversion illustrates the concept. Want more? Try LeetCode 191: Number of 1 Bits or LeetCode 338: Counting Bits. Ready to add? Visit Solve LeetCode 371 on LeetCode and sum those integers today!