不用加减乘除做加法
C++，位运算。
不能用四则运算实现加法，就只能用位运算来实现了。
在十进制中，加法的过程如下，例如a + b = 134 + 267：
- 加法包括按位相加以及进位
- 按位相加就是
[1 + 2 = 3， 3 + 6 = 9， 4 + 7 = 1]， 即a = [0, 3, 9, 1]； - 进位就是把和当成四位数来看
[0, 1 + 2 = 0, 3 + 6 = 0, 4 + 7 = 1]，然后移位得到b = [0, 0, 1, 0] - 然后继续按位相加
a = a + b = [0, 3, 0, 1]，继续进位移位b = a + b = [0, 1, 0, 0]； - 继续按位相加
a = a + b = [0, 4, 0, 1]，继续进位移位b = a + b = [0, 0, 0, 0]； - …
- 可以发现在b为全0的情况下，结果不会变了，也就是结果等于401
二进制同理，以下不再解释，仅模拟过程，解释同上，例如a + b = 5 + 7 = 0101 + 0111：
-
按位相加
[0 + 0 = 0, 1 + 1 = 0, 0 + 1 = 1, 1 + 1 = 0] = [0, 0, 1, 0] - 进位移位
[0 + 0 = 0, 1 + 1 = 1, 0 + 0 = 0, 1 + 1 = 1] = [1, 0, 1, 0] -
按位相加
[0 + 1 = 1, 0 + 0 = 0, 1 + 1 = 0, 0 + 0 = 0] = [1, 0, 0, 0] - 进位移位
[0 + 1 = 0, 0 + 0 = 0, 1 + 1 = 1, 0 + 0 = 0] = [0, 1, 0, 0] -
按位相加
[1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0, 0 + 0 = 0] = [1, 1, 0, 0] - 进位移位
[1 + 0 = 0, 0 + 1 = 1, 0 + 0 = 0, 0 + 0 = 0] = [0, 0, 0, 0] - ….
- 最后就是
[1, 1, 0, 0]，也就是12
熟悉位运算的人肯定看出来“按位相加”就是位运算里的按位异或^，”进位移位“就是位运算里的按位与和移位& + <<，所以只要到进位的数为0时终止“按位相加”和”进位移位“这两个步骤就行了。
class Solution {
public:
int Add(int num1, int num2) {
while (num2) {
int temp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = temp;
}
return num1;
}
};
