不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例：
输入: a = 1, b = 1
输出: 2
提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数
题目分析
这题我用了两种做法，分别复习 加法器 和 位运算，下面先看 加法器 版本：
- 加法器
- 初始化，结果为0，当前位为32bit int的最低位，也就是0x 1，进位为0
- a、b分别和当前位作 与 运算，结果代表a（b）的最后一位是否为1
- 下面分 2^3 中情况
3.1 a_now ！= 0，b_now ！= 0，c == 1，这相当于1+1+1，进位为1，当前位结果为1，
3.2 a_now ！= 0，b_now ！= 0，c == 0，这相当于1+1+0，进位为1，当前位结果为0，
3.3 a_now ！= 0，b_now == 0，c == 1，这相当于1+0+1，进位为1，当前位结果为0，
3.4 a_now ！= 0，b_now == 0，c == 0，这相当于1+0+0，进位为0，当前位结果为1，
3.5 a_now == 0，b_now ！= 0，c == 1，这相当于0+1+1，进位为1，当前位结果为0，
3.6 a_now == 0，b_now ！= 0，c == 0，这相当于0+1+0，进位为0，当前位结果为1，
3.7 a_now == 0，b_now == 0，c == 1，这相当于0+0+1，进位为0，当前位结果为1，
3.8 a_now == 0，b_now == 0，c == 0，这相当于0+0+0，进位为0，当前位结果为0， - 每计算一次，当前位左移一位，回到2
- int型有32位，只需要执行32遍就好
为了方便理解，这里我的 if-else 没有做简化和优化
public int add(int a, int b) {
int result = 0;
int c = 0;
int now = 1;
while(a != 0 && now != 0){
int lowA = a & now;
int lowB = b & now;
if(lowA != 0){
if(lowB != 0){
if(c == 1){
c = 1;
result |= now;
}else{
c = 1;
}
}else{
if(c == 1){
c = 1;
}else{
c = 0;
result |= now;
}
}
}else{
if(lowB != 0){
if(c == 1){
c = 1;
}else{
c = 0;
result |= now;
}
}else{
if(c == 1){
c = 0;
result |= now;
}
}
}
now <<= 1;
}
while(b != 0 && now != 0){
int lowB = b & now;
if(lowB != 0){
if(c == 1){
c = 1;
}else{
result |= now;
}
}else{
if(c == 1){
c = 0;
result |= now;
}
}
now <<= 1;
}
return result;
}
- 位运算
计算a + b时，进位可以用 （a & b）<< 1，来表示，当前位可以用（a ^ b）来表示，举个例子：
5 + 5 = 10
二进制形式：0101 + 0101 = 1010
（a ^ b） = 0000
（a & b）<< 1 = 0101 << 1 = 1010
（a ^ b）+ （a & b）<< 1 = 1010
可以表示为 当前位 加 进位
好像好有道理，但好像也没道理，因为还是需要计算（a ^ b）+ （a & b），里面有 + 法
那就用继续回到第一步，继续用这个方法来算这个 + 法呀，递归循环都好:
public int add(int a, int b) {
while (b != 0) {
int c = (a ^ b);
b = ((a & b) << 1);
a = c;
}
return a;
}
