leetcode

Sum of Two Integers

Sum of Two Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # 32 bits interger min
        MIN = 0x80000000
        # mask to get last 32 bits
        mask = 0xFFFFFFFF
        
        while b != 0:
            # ^ get different bits and & gets double 1s, << moves carry
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        
        # if a is negative, get a's 32 bits complement positive first
        # then get 32-bit positive's Python complement negative
        return a if a <= MAX else ~(a ^ mask)

~ x

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [204]: mask = 0xFFFFFFFF
In [205]: a = -1
In [206]: bin(a ^ mask)
Out[206]: '-0b100000000000000000000000000000000'
In [207]: bin(~(a ^ mask))
Out[207]: '0b11111111111111111111111111111111'
In [208]: (~(a ^ mask))
Out[208]: 4294967295
In [209]: 2 ** 32
Out[209]: 4294967296

负数的二进制表示方法

BitwiseOperators

leet code