371. Sum of Two Integers

题目描述和难度

  • 题目描述:

不使用运算符 +-,计算两整数a 、b之和。

示例:
若 a = 1 ,b = 2,返回 3。

致谢:
特别感谢 @fujiaozhu 添加这道问题并创建测试用例。

思路分析

求解关键:了解一些位运算的性质是解决这个问题的关键。

  • 既然不允许使用加法,那么位运算就是首选了。
  • 位运算中有一种运算叫做“半加运算”,也称作“无进位加法”,即是大名鼎鼎的“异或”运算。我们可以验证一下,“异或”运算是不是可以看成没有进位的加法。所以我们一定会用上它。
  • 接下来我们要解决的就是进位的问题了。那么什么时候进位呢,同为 1 的时候才进位,特殊处理同为 1 这件事情,就是“与”运算干的事情,进位是向高位进位,我们把“与”运算的结果左移 1 位就好了。
  • 注意:这种进位可能是接连进行的,所以要在一个循环中进行。
  • 如果“与”运算的结果是 0,那么循环就没有必要继续下去了。

参考解答

参考解答1

public class Solution {

    /**
     * 先做加法,其实就是异或运算
     * 再做进位
     * 1 0 1 1
     * 1 1 1 1
     * 异或: 0 1 0 0
     * 与运算 1 0 1 1
     *
     * @param a
     * @param b
     * @return
     */
    public int getSum(int a, int b) {
        int sum;
        while (true) {
            sum = a ^ b;
            int carry = a & b;
            if (carry == 0) {
                break;
            }
            a = sum;
            b = carry << 1;
        }
        return sum;
    }
}

参考解答2:同参考解答 1 ,写法不一样而已。

public class Solution2 {

    public int getSum(int a, int b) {
        int sum;
        int carry;
        do {
            sum = a ^ b;
            carry = a & b;

            a = sum;
            b = carry << 1;
        } while (carry != 0);
        return sum;
    }
}

参考解答3:同参考解答 1 ,写法不一样而已。

public class Solution3 {

    public int getSum(int a, int b) {
        int sum = 0;
        int carry = 0;
        while (true) {
            sum = a ^ b;
            // 括号不能丢
            carry = (a & b) << 1;
            if (carry == 0) {
                break;
            }
            a = sum;
            b = carry;
        }
        return sum;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0371-sum-of-two-integers ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com