leetcode_371

发表于   |   分类于

Sum of Two Integers

题目戳这

题意

给两个数a, b,求不用+运算符计算出a+b的结果

解法

这题目比较新颖，利用位运算来模拟加号，方法是用^来实现位相加，用&来实现位进位，当然进位的时候因为要向高位进位，所以&的结果要向左移位，我们来看一个例子:

比如6，5： 6的二进制110， 5的二进制101

  1. 110^101 = 011 , 110&101 = 100, 100向左移位100<<1 = 1000
  2. 011^1000 = 1011, 011&1000 = 0000

运算结束，结果就是1011=11，正确

但是由于python没有无符号右移，而且左移超过范围就会转变类型，所以我们这用C++会比较方便。

代码

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