问题描述
给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符
说明
a和b都是 32位 整数么？
- 是的
我可以使用位运算符么？
- 当然可以
样例
如果 a=1 并且 b=2，返回3
解题思路
以计算 5＋17＝22 为例：
在十进制加法中，我们可以分成三步进行：
1. 只做各位相加不进位，此时相加的结果是 12（个位数 5 和 7 相加不要进位是 2，十位数 0 和 1 相加结果是 1）；
2. 做进位，5+7 中有进位 1，进位的值是 10；
3. 按照第1步中的方法将进位值与第 1 步结果相加，得到最终结果 22。
下面考虑二进制数的情况（5＝101，17＝10001）：
仍然分3步：
1. 各位相加但不计进位，得到结果 10100；
2. 记下进位，本例中只在最后一位相加时产生进位 1，进位值为二进制的 10；
3. 按照第1步中的方法将进位值与第 1 步结果相加，得到最终结果 10110，转换成十进制正好是 22。
接下来把二进制的加法用位运算来替代：
1. 不考虑进位对每一位相加，0＋0＝0，0＋1＝1，1＋0＝1，1＋1＝0，注意到，这和异或的结果是一样的；
2. 考虑进位，只有在 1＋1 时会向前产生一个进位，此时可以想象成两个数先做位与运算，然后再向左移动一位，只有两个数都是 1 的时候，位与得到的结果是 1，其余都是 0；
3. 把前两个步骤的结果相加，相加的过程依然是重复前面两步，直到不再产生进位为止。
以上分析参考自<<剑指Offer>>。
解题代码
class Solution {
public:
/*
* @param a: The first integer
* @param b: The second integer
* @return: The sum of a and b
*/
int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
while(b != 0){
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}
};扩展进阶
用位运算实现减法运算
实现 a - b 只要实现 a + (-b) 即可，根据二进制数在机器中表达的规则，得到一个数的相反数，就是这个数的二进制数表达取反加1的结果。所以实现减法运算的代码如下：
int aminusb(int a, int b) {
int temp = aplusb(~b, 1);
return aplusb(a, temp);
用位运算实现乘法运算
a * b 的结果可以写成 a * 20 * b0 + a * 21 * b1 + … + a * 2i * bi + … + a * 231 * b31，其中，bi 为 0 或 1 代表整数 b 的二进制表达中第 i 位的值。
以 a = 22 = 10110, b = 13 = 1101为例:
用res来记录每次运算的结果，res = 0
a: 10110
b: 1101
b 的最低位为1， 所以res = res + a = 10110，同时 b 右移一位，a左移一位。
a: 101100
b: 110
b 的最低位为0， 所以res不变，同时 b 右移一位，a左移一位。
a: 1011000
b: 11
b 的最低位为1， 所以res = res + a = 1101110，同时 b 右移一位，a左移一位。
a: 10110000
b: 1
b 的最低位为1， 所以res = res + a = 100011110，同时 b 右移一位，a左移一位。
a: 101100000
b: 000000000
此时 b 为 0，过程停止，返回 res = 100011110，即 286。
所以实现乘法运算的代码如下:
int amultib(int a, int b) {
int res = 0;
while(b != 0){
if((b & 1) != 0)
res = aplusb(res, a);
a <<= 1;
b >>= 1;
}
return res;
}当然，这只适用于正数做乘法的情况，考虑负数的话代码应该为：
int amultib2(int a, int b) {
if(a < 0){
if(b < 0){
return amultib(aplusb(~a, 1), aplusb(~b, 1));
}else{
int temp1 = aplusb(~a, 1);
int temp2 = amultib(temp1, b);
return aplusb(~temp2, 1);
}
}else{
if(b < 0){
int temp1 = aplusb(~b, 1);
int temp2 = amultib(a, temp1);
return aplusb(~temp2, 1);
}else{
return amultib(a, b);
}
}
}用位运算实现除法运算
用位运算实现除法运算，其实就是乘法的逆运算。a / b 就是看 a 最多能减去多少个 b，所以正数除法的代码如下：
int adivb(int a, int b) {
int res = 0;
for(int i = 31; i >= 0; i = aminusb(i, 1))
if((a >> i) >= b){
res |= (1 << i);
a = aminusb(a, b << i);
}
return res;
}考虑到负数的情况，代码应该为:
int adivb2(int a, int b) {
if( b == 0){
cout << "除数不能为0" << endl;
exit(-1);
}
if(a < 0){
if(b < 0)
return adivb(aplusb(~a, 1), aplusb(~b, 1));
else{
int temp1 = aplusb(~a, 1);
int temp2 = adivb(temp1, b);
return aplusb(~temp2, 1);
}
}else{
if(b < 0){
int temp1 = aplusb(~b, 1);
int temp2 = adivb(a, temp1);
return aplusb(~temp2, 1);
}else
return adivb(a, b);
}
}以上除法分析可以算绝大多数的情况，但32位整数的最小值为-2147483648，最大值为2147483647，最小值的绝对值比最大值的绝对值大1，所以，如果a或b等于最小值，是转不成相应的正数的，