剑指Offer-不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解法

这里需要学习位运算的知识😀。

按位与&：有0则0，全1则1
按位或|：有1则1，全0则0
异或^：相同则0，不同则1

我们可以使用位运算来完成加法。

正常加法	异或
1 + 1 = 2	1 ^ 1 = 0 ❌
1 + 0 = 1	1 ^ 0 = 1 ✅
0 + 1 = 1	0 ^ 1 = 1 ✅
0 + 0 = 0	0 ^ 0 = 0 ✅

可以发现使用异或，只有1 + 1这里对不上，而这个问题是由于没有进位导致的🙄，如何计算进位呢？

| 按位与 |

|1 & 1 = 1 |
|1 & 0 = 0 |
|0 & 1 = 0 |
|0 & 0 = 0 |

与运算成功实现了进位，我们再把它左移一位，就真正的在计算上实现了进位。

再将使用异或计算的结果和与运算计算的结果加起来，然后再计算是否有进位，重复这个操作，直至进位为0，加法就计算完成了👀。

代码实现

public class Solution {
  public int Add(int num1, int num2) {
    // 结果和进位变量
    int result = 0;
    int carry = 0;
    do {
      // 无进位加法
      result = num1 ^ num2;
      // 计算进位
      carry = (num1 & num2) << 1;
      // 将值赋给num1, num2 进行循环
      num1 = result;
      num2 = carry;
    } while (carry != 0); // 使用do while可以使循环至少执行一次
    return result;
  }
}