Skip to content

371 sum of two integers

371. Sum of Two Integers

题目: https://leetcode.com/problems/sum-of-two-integers/

难度:

Easy

思路

谷歌答案

位运算

XOR
x   y output
0   0   0
1   0   1
0   1   1
1   1   0


AND
x   y   output
0   0   0
1   0   1
0   1   1
1   1   1   

如果对x和y来做加法(x和y都是一位的),那么末位会是x xor y,进位会是x and y

python没有左移,用c++来看

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0 ){
            int c = a & b;
            a = a ^ b;
            b = c << 1;
        }
        return a;
    }
};

实际上看到答案还是没有那么明白的,还是动手算算

a = 6   (0110)
b = 15  (1111)


1st
---------
carry = a & b = 0110
a = a ^ b = 1001
b = 1100


2nd 
---------
carry = a & b = 1000
a = a ^ b =  0101
b = 10000


3rd
----------

carry = a & b = 0
a = a ^ b = 10101
b = 0

这个时候a 的值是2^4 + 2^2 + 2^0 = 16+4+1 = 21  

虽然convence了我自己,但是表示依旧迷茫ing

也知道位运算需要待补啊



回到顶部