65. 不用加减乘除做加法【难】

---

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9865.%20%E4%B8%8D%E7%94%A8%E5%8A%A0%E5%87%8F%E4%B9%98%E9%99%A4%E5%81%9A%E5%8A%A0%E6%B3%95/README.md

面试题 65. 不用加减乘除做加法

题目描述

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

 

示例:

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

 

提示：

• a, b 均可能是负数或 0
• 结果不会溢出 32 位整数

解法

方法一：位运算

两数字 $a$, $b$ 求和。

假设 $a_i$ 和 $b_i$ 分别表示 $a$ 和 $b$ 的第 $i$ 个二进制位。一共有 $4$ 种情况：

$a_i$	$b_i$	不进位的和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察可以发现，“不进位的和”与“异或运算”有相同规律，而进位则与“与”运算规律相同，并且需要左移一位。

• 对两数进行按位 & 与运算，然后左移一位，得到进位；
• 对两数进行按位 ^ 异或运算，得到不进位的和；
• 问题转换为求：“不进位的数 + 进位” 之和；
• 循环，直至进位为 $0$，返回不进位的数即可（也可以用递归实现）。

时间复杂度 $O(\log M)$，空间复杂度 $O(1)$。其中 $M$ 为整数的最大值。

Python3

https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solutions/210882/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/
原码与补码的转换：正值不变
负值：原码取反+1=补码 补码符号位不变，其他位取反 + 1
0000 0011 3
1111 1001 -7
c=0000 0010
a=1111 1010
b=c
c=0000 0100【对应的进位】
a=1111 1000【无进位】
b=c
c=0000 0000
a=1111 1100
b=c
1111 1011
1000 0100

class Solution:def add(self, a: int, b: int) -> int:#正数的补码等于原码#-5在计算机中的64位表示：1111111111111111111111111111111111111111111111111111111111111011#通过掩码& 0xFFFFFFFF，获得低32位，对应-5的补码(原码取反 + 1)a, b = a & 0xFFFFFFFF, b & 0xFFFFFFFF  while b:c = ((a & b) << 1) & 0xFFFFFFFFa, b = a ^ b, creturn a if a < 0x80000000 else ~(a ^ 0xFFFFFFFF)

Java

class Solution {public int add(int a, int b) {while (b != 0) {int c = (a & b) << 1;a ^= b;b = c;}return a;}
}

C++

class Solution {
public:int add(int a, int b) {while (b) {unsigned int c = (unsigned int) (a & b) << 1;a = a ^ b;b = c;}return a;}
};

Go

func add(a int, b int) int {if b == 0 {return a}return add(a^b, (a&b)<<1)
}

TypeScript

function add(a: number, b: number): number {while (b) {const c = (a & b) << 1;a ^= b;b = c;}return a;
}

JavaScript

/*** @param {number} a* @param {number} b* @return {number}*/
var add = function (a, b) {if (b == 0) {return a;}return add(a ^ b, (a & b) << 1);
};

C#

public class Solution {public int Add(int a, int b) {while (b != 0) {int c = (a & b) << 1;a = a ^ b;b = c;}return a;}
}

Swift

class Solution {func add(_ a: Int, _ b: Int) -> Int {var a = avar b = bwhile b != 0 {let c = (a & b) << 1a ^= bb = c}return a}
}

方法二

Java

class Solution {public int add(int a, int b) {if (b == 0) {return a;}return add(a ^ b, (a & b) << 1);}
}