Leetcode-371-两整数之和

Leecode-371-Sum of Two Integers

思路：位运算

题目描述

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

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


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

Solution：位运算

• 在二进制中的计算就是通过位操作来得到结果的低位和高位

a	b	低位	高位
0	0	0	0
1	0	1	0
0	1	1	0
1	1	0	1

• 从上面表格可以发现
  • 低位是 a ^ b
  • 高位是 a & b

• 回想一下在十进制的计算中，如果进位一直大于0，就得往后面进行计算，在这里也是一样。
• 只要进位不是0，那么我们就得一直重复计算低位和进位的操作（需要在下一次计算之前把进位向左移动一位，这样进位才能和更高位进行运算。）
• 这个时候的a 和 b 就是刚才计算的低位和高位

Java

Solution :

// 二进制的计算中就是要通过位操作来得到结果的低位和进位
// 低位 = a^b，进位 = a & b
class Solution {
    public int getSum(int a, int b) {
        if (a == 0){
            return b;
        }

        if (b == 0){
            return a;
        }

        int lower = 0;
        int carrier = 0;

        // 只要进位不是0，就得一直重复计算低位和进位的操作
        while (true){
            lower = a^b;  // 计算低位
            carrier = a&b; // 计算进位

            if (carrier == 0){
                break;
            }

            a = lower;
            b = carrier<<1; // 需要在下一次计算之前要把进位向左移动一位,这样进位才能和更高位进行运算
        }

        return lower;
    }
}

测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.getSum(9, 8));
}

• 时间复杂度 ： O(1) 计算进位的时间
• 空间复杂度 ： O(1) 不需要额外的空间

Python

Solution :

打赏