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.
不用+和-号,其实也就是用其他运算符来模拟这个实现过程;Java中最重要的一种工具就是位运算:
& | ^ ~
及移位运算符。
- 加法:将两个数看作是二进制数,利用
- 相异(^)时,本位为1,进位为0;
- 同为1时本位为0,进位为1;同为0时,本位进位均为0.
所以,不计进位的和为sum = a^b,进位就是ans = a&b,(与sum相加时先左移一位,因为这是进位)。完成加法直到进位为0。
例: a=2—> 10 b=2–>10
- a+b : ans=a&b=10 不进位和sum=a^b=0;
- ans左移一位+sum=100-->4
- 减法:利用a+(-b)来实现,其中-b为补码,及取反再加一
- 乘法:循环利用加法,实现b个a相加
- 整数除法:循环相减,直至减至非正数。
- 模运算:同上
public int getSum(int a, int b) {
if(b==0) return a;
int ans=0;
while(b!=0){
ans=a^b;
b=(a&b)<<1;
a=ans;
}
return ans;
}