1.原题
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.(计算两个数的和,但是不能用+和-操作符)
Example:
Given a = 1 and b = 2, return 3.
2.思路
不允许用+、-操作符,那么暂且只能想到位运算来入手。
1.”&”与操作符, 2 (0010) & 7 (0111) => 2 (0010)
“^” XOR(异或) operation, 2 (0010) ^ 7 (0111) => 5 (0101)
2. a+b 不考虑进位的话则是相当于 a xor b的操作。(0001+0011=0010 不考虑进位)
3. 进位则可以看做 (a & b) << 1.
4. 因此模仿a+b的真实操作则是,(a xor b) + ( (a&b)<<1 ),这时候如果( (a&b)<<1 )进位不为0,那么肯定要继续相加,所以可以递归调用,也可以while循环直到进位为0的时候。
3.AC解
public class Solution {
public int getSum(int a, int b) {
if(a==0) return b;
if(b==0) return a;
int carry = 0;
while(b!=0){
carry = a & b;
a = a ^ b; //xor位相加不进位,并赋给a
b = carry << 1; //计算进位,并赋给b,然后循环 a+b,直到b为0,无进位
}
return a;
}
}
4.优秀Discuss
// Iterative
public int getSum(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
// Iterative减法
public int getSubtract(int a, int b) {
while (b != 0) {
int borrow = (~a) & b;
a = a ^ b;
b = borrow << 1;
}
return a;
}
// Recursive
public int getSum(int a, int b) {
return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}
// Recursive
public int getSubtract(int a, int b) {
return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}
// Get negative number
public int negate(int x) {
return ~x + 1;
}