LC-Sum of Two Integers

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
         # 32 bits integer max
        MAX = 
        # 32 bits interger min
        MIN = 
        # mask to get last 32 bits
        mask = 
        while b != :
            # ^ get different bits and & gets double 1s, << moves carry
            a, b = (a ^ b) & mask, ((a & b) << ) & 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)

Sol = Solution()
print Sol.getSum(,)
           

0，LC中他人的可行方法

1，首先，題目要求在不使用+ 和 - 的情況下實作整數的相加減。參考資料後，得知其本質為模拟計算機内部的整數加減形式。

首先，我們通過對x和y進行&位運算，得出每一位上的進位。然後對x和y進行^位運算，得出沒有加進位的和。最後将所得的和當做新的x，所得的進位往左移一位(第零位的進位輸入為0)當做新的y，繼續做上面的步驟，直到進位為0，此時x中儲存的就是我們要求的x和y的和了。

進位左移，然後與原先的結果進行相加。

2，在給定的方法中，大緻的思想是這樣的，但是還有點不同。因為在python中，它的整型的範圍是不止32位的，貼上作者的解釋：

Python has more than 32 bits for integers. You can try to run “print 2 * 31”and Python would shows the exact number correctly, while other languages like Java would not. Java only recognizes -2 * 31 to 2 ** 31 - 1.

How does integers presented in Python differ from integers in 32-bit e.g. Java?

From what I heard, Python has 64 bits. (Please let me know if I am wrong. )

So 1 in Python would look like 0x0000000000000001, but it looks like 0x00000001 in 32-bit format.

-1 in Python would look like 0xFFFFFFFFFFFFFFFF, but it looks like 0xFFFFFFFF in 32-bit format.

It seems that the input given by LC is in 32-bit format. Since Python would treat it as positive with 1 on the 32 position, we have to use mask to treat it as negative.

For example, if a is -2 after the loop, a would be 0x00000000FFFFFFFE. What ^mask does here is get a’s 32-bit complement, so a^mask = 0x0000000000000001. FYI, this is exactly what ~ in Java would do, -2 in Java is 0xFFFFFFFE, its 32-bit complement is 0x00000001 in Java. Since the output needs to be in 64-bit to be check by OJ, we want 64-bit -2. ~ in Python would convert 0x0000000000000001 to 0xFFFFFFFFFFFFFFFE, which is -2 in Python.

In sum, you can consider a^mask gets a’s 32-bit positive complement with more 32-bit 0’s on left, and ~ gets the common Python complement.

Basically, this OJ gives us 32-bit integers as input and expects 64-bit integers as output.