AcWing 85. 不用加减乘除做加法
题目链接:
tags:位运算 二进制
解题思路:
加法要考虑3种情况:
- 不进位加法:如十进制的1+5,二进制的 1+ 0
- 进位加法:如十进制的9+5,二进制的1+1
- 原本不进位,前面的数进位相加之后进位:如十进制的99 + 2,二进制的11+1
一位数相加的所有可能,如A+B = C。D表示进位的值,可以列表:
A | 0 | 0 | 1 | 1 |
---|---|---|---|---|
B | 0 | 1 | 0 | 1 |
C | 0 | 1 | 1 | 0 |
D | 0 | 0 | 0 | 1 |
可以得出不进位加法:C = A ^ b
进位值:D = A & B
将加法分为两个部分考虑:
- 不进位加法的值
- 进位的值
因为加法具有交换律,所以可以将加法运算拆分乘两部分之后相加,结果相同。
十进制:15+8 可以拆分为两个部分
1. 第一部分不进位加法:15+8 = 13 2. 第二部分进位数乘以10: 1 * 10 = 10
相加的13+10 = 23
二进制:11 + 01 可拆分为两部分
- 第一部分不进位加法:11 ^ 01 = 10
- 第二部分进位乘以2: (11 & 01) << 1 = 10
10+10 = 100
但是不能使用加法进行运算,所以并不能直接使用C + D
而要实现C+D的操作,重复使用上面的操作
直到D == 0,那么就表示无进位,而使用不进位加法即可算出答案,则结束。
例子:
1011 + 11
①A ^ B = C = 1000
②A & B << 1 = D = 0110
③C ^ D = C = 1110
④C & D << 1= D = 0000
所以: 1011+11 = 1110
证明:D最终会等于0
因为每次循环D都会往前移动一位,所以每次迭代D都会比之前多一个0,最多迭代32次,就会将D全变成0.
C++ 代码
class Solution {
public:
int add(int num1, int num2){
while(num2!=0){
int sum = num1 ^ num2;//不进位的加法
int carry = (num1 & num2)<<1;//进位
num1 = sum;
num2 = carry;
}
return num1;
}
};