[每日一题] 第六题：不用加减乘除做加法
0 / 0 / 创建于 4年前 /
DRose 的个人博客
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数题解
方法一：位运算
解题思路
本题考查对位运算的灵活使用，即使用位运算实现加法。
设两数字的二进制形式 a，b，其求和 s = a + b，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：
| a(i) | b(i) | 无进位和 n(i) | 进位 c(i+1) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
观察发现，无进位和 与 异或运算 规律相同，进位 与 与运算 规律相同（并需左移一位）。因此，无进位和 n 与进位 c 的计算公式如下：
n = a ⊕ b 非进位和：异或运算
c = a & b << 1 进位：与运算 + 左移一位（和 s）= （非进位和 n） + （进位 c）。即可将 s = a + b 转化为：s = a + b => s = n + c
循环求 n 和 c，直至进位 c = 0；此时 s = n，返回 n 即可。
![[每日一题] 第六题：不用加减乘除做加法](https://cdn.learnku.com/uploads/images/202007/31/61979/OXiVnguMOQ.png!large)
Q ： 若数字 aa 和 bb 中有负数，则变成了减法，如何处理？
A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。
代码
class Solution {
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
}复杂度分析
时间复杂度O(1) ：最差情况下（例如 a = 0x7fffffff，b = 1 时），需循环 32 次，使用 O(1) 时间；每轮中的常数次位操作使用 O(1) 时间。
空间复杂度O(1) ：使用常数大小的额外空间。
个人理解
以 9 + 7 为例，详细手动模拟一下步骤：
十进制模拟
第一次循环，计算 9 + 7：
无进位和：9 + 7 = 6。
进位：个位进一位为 1，进到十位了，所以要 * 10，即 10。
第二次循环，计算 6 + 10：
无进位和：
个位：0 + 6 = 6
十位：1 + 0 = 1
结果为 16
进位：个位无进位，十位无进位，
所以最终结果为 16。
二进制模拟
9 的二进制为：1001
7 的二进制位：111
第一次循环，计算 1001 + 111：
无进位和（异或）：1001 ^ 111 = 1110
进位（与）：1001 & 111 = 1
十进制进位就应该 x10，二进制进位就得左移一位，所以 1 << 1 = 10
第二次循环，计算 1110 + 10：
无进位和（异或）：1110 ^ 10 = 1100
进位（与）：1110 & 10 << 1 = 10 < < 1 = 100
第三次循环，计算 1100 + 100：
无进位和（异或）：1100 ^ 100 = 1000
进位（与）：1100 & 100 << 1 = 100 < < 1 = 1000
第四次循环，计算 1000 + 1000：
无进位和（异或）：1000 ^ 1000 = 0000
进位（与）：1000 & 1000 << 1 = 1000 < < 1 = 10000
第五次循环，计算 0000 + 10000：
无进位和（异或）：0000 ^ 10000 = 10000
进位（与）：0000 & 10000 << 1 = 00000 < < 1 = 000000
这个时候就该结束了，因为此时无进位了。
此时 10000 的值就是最终结果，换成十进制为 16。
为什么十进制相加循环次数这么少？而二进制循环次数这么多呢？ 因为二进制位数多，碰到特别情况，比如该情况，一位一位向上进，所以循环次数就多了。
那么什么时候结束循环呢？ 就是没有进位的时候，不需要再加了。
为什么要有循环呢？ 因为相加就会产生进位，进位了说明没算完，需要继续加上进位，知道没有进位。
题解来源
作者：jyd
链接：leetcode-cn.com/problems/bu-yong-j...
来源：力扣（LeetCode）
方法二：奇思妙想解法
代码
真没有运算符！！
class Solution:
def add(self, a: int, b: int) -> int:
result = [a,b]
return sum(result)题解来源
作者：luyao777
链接：leetcode-cn.com/problems/bu-yong-j...
来源：力扣（LeetCode）
来源
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/bu-yong-j...
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号