371. Sum of Two Integers

题目描述和难度

• 题目描述：

• 题目难度：简单。
• 英文网址：371. Sum of Two Integers 。
• 中文网址：371. 两整数之和 。

思路分析

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

• 既然不允许使用加法，那么位运算就是首选了。
• 位运算中有一种运算叫做“半加运算”，也称作“无进位加法”，即是大名鼎鼎的“异或”运算。我们可以验证一下，“异或”运算是不是可以看成没有进位的加法。所以我们一定会用上它。
• 接下来我们要解决的就是进位的问题了。那么什么时候进位呢，同为 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 。