[剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录
第 65 题：不用加减乘除做加法
传送门： 不用加减乘除做加法，牛客网 online judge 地址。
写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。
样例：
输入：
num1 = 1 , num2 = 2输出：3
思路：不用加减乘除，那就只能用位运算了。
《剑指 Offer （第 2 版）》第 65 题：不用加减乘除做加法-1
下面是交换两个数的特殊写法，了解一下。
《剑指 Offer （第 2 版）》第 65 题：不用加减乘除做加法-2
Python 代码：在 Python 内部对整数的处理分为普通整数和长整数，普通整数长度为机器位长，通常都是 位，超过这个范围的整数就自动当长整数处理，而长整数的范围几乎完全没限制。
Python 代码：
class Solution(object):
def add(self, num1, num2):
"""
:type num1: int
:type num2: int
:rtype: int
"""
while num2 != 0:
# 不进位加法
temp = num1 ^ num2
# 加法进位
num2 = (num1 & num2) << 1
# 把高于 32 位的 1 全部变成 0
num1 = temp & 0xFFFFFFFF
return num1 if num1 >> 31 == 0 else num1 - (1 << 32)
说明：Python 中 int 类型的最大值是 0x7fffffff。
Python 代码：与上面的写法等价
class Solution(object):
def add(self, num1, num2):
"""
:type num1: int
:type num2: int
:rtype: int
"""
while True:
# 不进位加法
s = num1 ^ num2
# 计算进位
carry = num1 & num2
# 手动把高于 32 位的部分变成 0
num1 = s & 0xFFFFFFFF
num2 = carry << 1
if carry == 0:
break
# 如果是正数和 0 ，就直接返回这个正数好了
if num1 >> 31 == 0:
return num1
# 如果是负数
return num1 - (1 << 32)
Java 代码：
public class Solution {
public int Add(int num1, int num2) {
int sum = 0;
while (true) {
// 计算个位
sum = num1 ^ num2;
int carry = num1 & num2;
if (carry == 0) {
break;
}
num1 = sum;
// 计算进位
num2 = carry << 1;
}
return sum;
}
public static void main(String[] args) {
Solution solution = new Solution();
int add = solution.Add(14, 15);
System.out.println(add);
}
}
还可以用“全加器”实现。
《剑指 Offer （第 2 版）》第 65 题：不用加减乘除做加法-3
Python 代码：
class Solution(object):
def add(self, num1, num2):
"""
:type num1: int
:type num2: int
:rtype: int
"""
# 特判
if num1 == 0 or num2 == 0:
return max(num1, num2)
res = 0
# 进位
carry = 0
for i in range(32):
a = num1 & (1 << i)
b = num2 & (1 << i)
# 不进位的和
s_ = (a ^ b) ^ carry
# 下面计算进位，三者之中，任意两者同为 1 的时候，就可以进位
carry = (a & b) | (a & carry) | (b & carry)
carry <<= 1
res += s_
if res >> 31 == 0:
return res
return res - (1 << 32)
Java 代码：
public class Solution {
public int Add(int num1, int num2) {
int sum = 0;
while (true) {
sum = num1 ^ num2;
int carry = num1 & num2;
if (carry == 0) {
break;
}
num1 = sum;
num2 = carry << 1;
}
return sum;
}
public static void main(String[] args) {
Solution solution = new Solution();
int add = solution.Add(14, 15);
System.out.println(add);
}
}
Java 代码：
public class Solution2 {
// 书上的写法
public int Add(int num1, int num2) {
int sum = 0;
int carry = 0;
do {
sum = num1 ^ num2;
carry = num1 & num2;
num1 = sum;
num2 = carry << 1;
} while (carry != 0);
return sum;
}
}
