剑指Offer65.不用加减乘除做加法

• 题目：剑指Offer65.不用加减乘除做加法
  求两个int类型数a+b；
  结果不会溢出 32 位整数

• 思路：
  这种限制±*/操作符，或者限制if，else，for，while语句的题，可选的方式往往有：利用&&或||的短路效应，位运算

1.位运算：
将求a+b转换为求进位部分+不进位部分；
进位部分：要找到a和b的对应二进制位均为1的地方（用&），然后<<1，就相当于进位操作；
不进位部分：a ^ b本身就被称为不进位加法；
用a和b分别代表进位部分和不进位部分，不断循环，直至其中一个为0，则另一个就是a+b；
之所以选b作为循环条件，因为b一定最终变为0：假如b的二进制末尾有k个0，则b = (a & b) << 1至少有k+1个0，因此最多循环2次b一定为0；而a要想为0，则必须a==b，这种情况不是每次都能出现；

class Solution {
public:
int add(int a, int b) {
while (b) {
//这里转成unsigned, 因为负数左移补1，而我们想让它补0
int c = unsigned(a & b) << 1;//进位部分,即对应二进制位是1 1时,使用&找到1 1 的位，之后 << 1将其加到前一位上
a ^= b;//不进位部分：对应二进制位是1 0得1，0 1得1，0 0得0，1 1得0，因此用 ^
b = c;//相当于将求a+b转换为求进位部分+不进位部分，但转换之后相加依然可能需要进位，因此循环至其中一部分为0停止
}
return a;
}
};

最后

以上就是自觉草丛为你收集整理的剑指Offer65.不用加减乘除做加法的全部内容，希望文章能够帮你解决剑指Offer65.不用加减乘除做加法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。