java位运算实现加减取模

2019-04-13 15:47发布

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; }