LeetCode: 371 Sum of Two Integers

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

Example:

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

Example:

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

问题

给定两个整数 a 和 b，在不使用 + 和 - 运算符的情况下，返回两个整数的和。

解决方案 1

位操作法

Approach 1 / 方法 1

This solution uses bitwise operations to perform the sum of two integers. The idea is to use XOR (^) to add the numbers without carrying, and AND (&) followed by a left shift to calculate the carry. This process is repeated until there is no carry left.

该解决方案使用位操作来实现两个整数的求和。其思想是使用异或运算 (^) 来相加数字但不进位，并使用与运算 (&) 后加上左移来计算进位。这个过程重复进行，直到没有进位为止。

Implementation / 实现

python

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32-bit mask in hexadecimal
        MASK = 0xFFFFFFFF
        # 32-bit max int
        MAX_INT = 0x7FFFFFFF

        while b != 0:
            # Calculate carry
            carry = (a & b) << 1
            # Add without carry
            a = (a ^ b) & MASK
            # Assign carry to b
            b = carry & MASK

        # If a is negative, return its two's complement
        return a if a <= MAX_INT else ~(a ^ MASK)

Explanation / 解释

1. Define a 32-bit Mask / 定义32位掩码

   MASK = 0xFFFFFFFF

   • English: We define a mask to handle 32-bit integer overflow. This mask ensures that the result remains within 32 bits.
   • Chinese: 我们定义一个掩码来处理32位整数溢出。这个掩码确保结果保持在32位以内。

2. Define 32-bit Maximum Integer / 定义32位最大整数

   MAX_INT = 0x7FFFFFFF

   • English: We define the maximum positive value for a 32-bit signed integer.
   • Chinese: 我们定义了32位有符号整数的最大正值。

3. Iterate Until There is No Carry / 循环直到没有进位

   while b != 0:

   • English: We iterate while there is a carry (b is not 0).
   • Chinese: 我们在有进位（b 不为 0）时进行循环。

4. Calculate the Carry / 计算进位

   carry = (a & b) << 1

   • English: We calculate the carry by performing an AND operation between a and b, then left-shifting the result by 1.
   • Chinese: 我们通过对 a 和 b 进行与运算，然后将结果左移1位来计算进位。

5. Add Without Carry Using XOR / 使用异或运算不带进位相加

   a = (a ^ b) & MASK

   • English: We update a with the result of XORing a and b, masked to ensure it fits within 32 bits.
   • Chinese: 我们使用 a 和 b 的异或运算结果更新 a，并使用掩码确保其在32位以内。

6. Update b to Carry / 将 b 更新为进位

   b = carry & MASK

   • English: We update b to the carry value, masked to fit within 32 bits.
   • Chinese: 我们将 b 更新为进位值，并使用掩码确保其在32位以内。

7. Handle Negative Numbers Using Two's Complement / 使用二进制补码处理负数

   return a if a <= MAX_INT else ~(a ^ MASK)

   • English: If a is greater than MAX_INT, it means the result is negative, so we return its two's complement.
   • Chinese: 如果 a 大于 MAX_INT，则表示结果为负数，因此我们返回其二进制补码。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(1), since the number of iterations is fixed and limited to the number of bits (32).
• Space Complexity / 空间复杂度: O(1), as no extra space is used except for a few variables.

Key Concept / 关键概念

• Bitwise Operations / 位操作: This approach leverages the properties of bitwise operations to perform addition without using the + operator.
• 位操作: 这种方法利用位操作的特性来实现不使用 + 运算符的加法。

解决方案 2

递归法

Approach 2 / 方法 2

This solution uses a recursive approach to perform the addition. The base case is when there is no carry (b == 0), and the recursive case calculates the sum without carry using XOR and the carry using AND and shifts.

该解决方案使用递归方法来实现加法。基本情况是没有进位（b == 0），递归情况使用异或运算计算不带进位的和，使用与运算和移位计算进位。

Implementation / 实现

python

class Solution:
    def getSum(self, a: int, b: int) -> int:
        if b == 0:
            return a
        return self.getSum((a ^ b) & 0xFFFFFFFF, ((a & b) << 1) & 0xFFFFFFFF)

Explanation / 解释

1. Base Case: No Carry / 基本情况：没有进位

   if b == 0:
      return a

   • English: If there is no carry (b == 0), we return a as the result.
   • Chinese: 如果没有进位（b == 0），我们返回 a 作为结果。

2. Recursive Case: Calculate Sum and Carry / 递归情况：计算和与进位

   return self.getSum((a ^ b) & 0xFFFFFFFF, ((a & b) << 1) & 0xFFFFFFFF)

   • English: We recursively calculate the sum without carry using XOR and mask it to fit within 32 bits. We calculate the carry using AND, shift it left by 1, and mask it to fit within 32 bits, then pass both to the next recursive call.
   • Chinese: 我们递归地使用异或运算计算不带进位的和，并使用掩码确保其在32位以内。我们使用与运算计算进位，左移1位后，再使用掩码确保其在32位以内，然后将两者传递给下一个递归调用。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(1), as the recursion depth is limited by the number of bits (32).
• Space Complexity / 空间复杂度: O(1), since we only use a constant amount of space for the recursion stack.

Key Concept / 关键概念

• Recursion and Bitwise Operations / 递归与位操作: This approach combines recursion with bitwise operations to perform addition, making it elegant and concise.
• 递归与位操作: 这种方法结合了递归和位操作来实现加法，使其优雅而简洁。

Comparison / 比较

1. Efficiency / 效率:

   • Iterative Bitwise Approach / 迭代位操作法: More straightforward and efficient for those who prefer loop-based solutions.
   • Recursive Approach / 递归方法: More elegant but can be less intuitive due to recursion.

2. Use Case / 使用场景:

   • Iterative / 迭代: Preferred for performance-critical applications where recursion depth might be a concern.
   • Recursive / 递归: Preferred for those who appreciate clean and concise code.

Summary / 总结

• English: Both the iterative bitwise and recursive approaches are effective for adding two integers without using +. The iterative method is more straightforward, while the recursive method is more elegant

.

• Chinese: 迭代位操作法和递归方法都能有效地在不使用 + 的情况下实现两个整数的加法。迭代方法更直观，而递归方法更优雅。

Tips / 提示

• English: Use the iterative approach for better control over the process, especially when working in environments where recursion depth is limited.
• Chinese: 在需要更好地控制过程的情况下使用迭代方法，特别是在递归深度有限的环境中。

Solution Template for Similar Questions / 提示

• English: Consider both iterative and recursive approaches for bit manipulation problems depending on the problem's constraints and requirements.
• Chinese: 根据问题的限制和要求，考虑迭代和递归方法处理位操作问题。

5 More Similar Questions / 推荐5问题

1. LeetCode 136. Single Number
2. LeetCode 191. Number of 1 Bits
3. LeetCode 260. Single Number III
4. LeetCode 268. Missing Number
5. LeetCode 29. Divide Two Integers

Recommended Resources / 推荐资源

• English: Practice both iterative and recursive approaches to bitwise operations to understand different ways to solve problems without using standard arithmetic operators.
• Chinese: 练习迭代和递归方法处理位操作问题，了解不同的方法来在不使用标准算术运算符的情况下解决问题。

Sum of Two Integers - Leetcode 371 - Java by NeetCode