剑指 Offer 65: 不用加减乘除做加法

[songyy5517]

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

分析 一开始并没有什么头绪，但运算符一共就那么几个。我首先想到了二进制的加法，其中共包含4种情况：

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0 (进位) 因此，我们可以用异或 (^)运算来模拟各个数位上的加法操作。 那么如何实现进位呢？进位也有4种情况：
• 0 + 0 = 无进位 (0)
• 0 + 1 = 无进位 (0)
• 1 + 0 = 无进位 (0)
• 1 + 1 = 有进位 (1) 因此，我们可以用与 (&)运算来模拟进位。此外，进位其实就是把高位加1，为了实现对高位的操作，我们还需要将结果左移一位。 综上，num1 + num2 等价于:
  1. sum = num1 ^ num2 （数位相加）
  2. carry = (num1 & num2) << 1 （实现进位）
  3. result = sum + carry (又回到了加法，因此需要循环进行上述操作，直到不产生进位carry = 0)

[songyy5517]

思路：分解加法 & 位运算

1. 循环计算两数之和，直到不产生进位：
   • 异或两个数（二进制）得到结果 $xor$ ；（不能直接赋给 $num1$ ，因为会影响下一步与的结果）
   • 两个数取与，再左移1位，得到结果2，并直接赋值给 $num2$ ；
   • 将 $xor$ 赋给 $num1$ 。
2. 返回 $num1$ 。

复杂度分析

• 时间复杂度： $O(1)$ ，最坏情况下a,b为 $2^{31} - 1$ ，需要对两个数的32个二进制数位进行位运算，使用 $O(1)$ 时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;
public class Solution {
    public int Add(int num1,int num2) {
        // 思路：一开始有点没头绪。但运算符一共就那么几个。
        // 我首先想到了二进制的加法，通过例子，决定使用XOR操作实现加法。

        while (num2 != 0){
            int carry = num1 ^ num2;    // 相加
            num2 = (num2 & num1) << 1;    // 进位
            num1 = carry;
        }

        return num1;
    }
}

[songyy5517]

Key points

1. 将加法分解成三步；
2. 相加不进位：^；
3. 进位：& << 1

[songyy5517]

2024/4/23

• 计算机内部统一用补码存储正负数，因此负数不必单独考虑。
• 运算符优先级： >> > &