题目

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2

*提示:

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

思路分析

分解

对于一个二进制的数a和b,任何一个位置上的二进制位位a(i) 和b(i),那么对于这个位置上的加法可以有如下的表示:其中c(i)表示进位:

a(i) b(i) n(i) c(i)
1 0 1 0
0 1 1 0
0 0 0 0
1 1 0 1

通过上面的表格其实可以看出,对于任何一位上的和的计算都是:两位之和再加上进位,对于表达式可以表示如下:
res = a+b = n + c;
其中n就是a和b的每一位都进行异或:n = a^b; c位每一位与并进行左移一位;这样对于两个数的和就可以表示为不停的看看是否存在进位,每次异或结束以后都要发现是否存在下一个进位;

代码实现

  1. class Solution {
  2. public int add(int a, int b) {
  3. while(b !=0){
  4. int c = (a & b) << 1;
  5. a = a^b;
  6. b = c;
  7. }
  8. return a;
  9. }
  10. }