ChunNote
0%

leetCode-371:Sum of Two Integers

发表于 分类于

问题描述

给定两个整数，要求在不使用加减法的情况求两数之和。题目链接：**点我**

样例输入输出

输入：a = 1, b = 2;

输出：3

输入：a = 3, b = 4

输出：7

问题解法

此题要求不能使用加减法，那就意味着需要使用位运算，使用半加器的思路，用与运算求出当前位的进位，用异或运算求出当前位相加后的值，由于进位需要向前移动一位和前一位的值进行运算，因此可以使用 (a & b) << 1 的值参与前一位的运算。代码如下

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

参考资料

https://leetcode.cn/problems/sum-of-two-integers/solution/liang-zheng-shu-zhi-he-by-leetcode-solut-c1s3/