offer-65


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

示例:

输入: a = 1, b = 1
输出: 2

提示:

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

预备知识

有符号整数通常用补码来表示和存储,补码具有如下特征:

  • 正整数的补码与原码相同;负整数的补码为其原码除符号位外的所有位取反后加 1。
  • 可以将减法运算转化为补码的加法运算来实现。
  • 符号位与数值位可以一起参与运算。

思路和算法

虽然题目只要求了不能使用运算符 +、-、* 和 /,但是原则上来说也不宜使用类似的运算符 +=、-=、*= 和 /=,以及 sum 等方法。于是,我们使用位运算来处理这个问题。

首先,考虑两个二进制位相加的四种情况如下:

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

文章作者: 倪春恩
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 倪春恩 !