【Python】 BEST LeetCode 371 Explanation for Python
First, this problem is not intended to be so difficult, but a weird feature of Python makes it unnecessarily troublesome. I\'ll assume you have learned the basi
First, this problem is not intended to be so difficult, but a weird feature of Python makes it unnecessarily troublesome. I\'ll assume you have learned the basic ideas for adding integers using bit operations. Namely, take the \'uncarried\' sum `a^b` and add to it the carry  `(a&b)<<1`. If you have questions about this, I suggest this video https://www.youtube.com/watch?v=qq64FrA2UXQ&t=848s\n\nThis post, however, will focus on why this simple idea cannot be implemented smoothly using Python.\n\nLet\'s see a java version of the solution:\n```\nclass Solution {\n    public int getSum(int a, int b) {\n        while (b != 0) {\n            int sum = a ^ b;\n            int carry = (a & b) << 1;\n            a = sum;\n            b = carry;\n        }\n        return a;\n    }\n}\n```\n\nThe correctness of this version relies on the fact that integers have **fixed** length (32 bits) in java. So `carry` (or `b`) will eventually be moved out of boundary and go to 0, and you can get out of the while loop. This is NOT the case for the Python! Python allows unlimited length of integers. If you try to mimic the code above, you will get to infinite loop!\n\n(*It is not very important but there is still a maximum integer in Python, although you can leftshift a bit infinitely many times*).\n\nSo what do we do? The first step is to manually bound the length of `sum` and `carry` by setting up a mask `0xFFFFFFFF`. `&` this mask with an (very long) integer will only keep the last 32 bits. Then, at each step of the loop, we `&` `sum` and `carry` with this mask, and eventually `carry` will be wiped out once it goes beyond 32 bits.\n\nThe Python code so far is\n```\nclass Solution(object):\n    def getSum(self, a, b):\n        """\n        :type a: int\n        :type b: int\n        :rtype: int\n        """\n        mask = 0xffffffff\n        while b:\n\t\t    sum = (a^b) & mask\n\t\t\tcarry = ((a&b)<<1) & mask\n            a = sum\n\t\t\tb = carry\n        \n        # Warning: this return statement is not correct yet!!!\n\t    return a\n```\n\nBUT this is not the whole story. Although we successfully get out of the while loop, sadly a consequence is that the value of `a` also has only 32 bits. If it is a non-negative value then we are fine, but we will **lose information** if it is negative in the normal sense! \n\nFor example, for the testcase `a = -12, b=-8`. We know the finally answer is `-20`, and the current code will produce 32 bits `0xFFFFFFEC` which looks like `-20` in our usual sense. Well, Python doesn\'t think so! Python believes this is a large positive integer `4294967276`, because all the bits to the far left are 0.\n\nSo what is the true representation of `-20 ` is in Python? I don\'t know the exact answer but logically since integers have "infinite" length, it can be thought of as `0x...FFFFFFFFFFFFFFEC` where there are infinitely many `F`.\n\nAt this moment, what we want to do it to convert the 32 bits sense `0xFFFFFFEC` to the infinite bits sense `0x...FFFFFFFFFFFFFFEC`. We can achieve this by using **two\'s complements**. First, we take the two\'s complement of `-20` in the 32 bits sense. This gives us a nice, positive `20` which is valid no matter how many bits we are using. Then, we take the two\'s complement of `20` is the infinite bits sense. This will produce a `-20` that Python can interpret.\n\nLet\'s recall the rule for taking two\'s complements: **Flip all the bits, then plus one**.\n\nSo, to take the two\'s complement of `-20` in the 32 bits sense. We flip all the 32 bits of `0xFFFFFFEC` and add 1 to it. Note that here we cannot use the bit operation `~` because it will flip infinite many bits, not only the last 32. Instead, we ` xor` it with the mask `0xFFFFFFFF`. Recall that `xor` with 1 has the same effect as flipping. This only flips the last 32 bits, all the 0\'s to the far left remains intact. Then we add 1 to it to finish the two\'s complement and produce a valid `20`\n```\n(0xFFFFFFEC^mask)+1 == 0x14 == 20\n```\n\nNext, we take the two\'s complement of `20` in the Python fashion. Now we can direcly use the default bit operation\n```\n~20+1 == -20\n```\n\nWrite these two steps in one line\n```\n~((0xFFFFFFEC^mask)+1)+1 == -20 == 0x...FFFFFFFFFFFFFFEC\n```\n\nWait a minute, do you spot anything weird? We are not supposed to use `+` in the first place, right? Why are there two `+1`\'s? Does it mean this method won\'t work? Hold up and let me give the **final magic** of today:\n\nfor any number `x`, we have\n```\n~(x+1)+1 = ~x\n```\n\n(*Here the whole* `(0xFFFFFFEC^mask)` *is considered as* `x`).\n\nIn other words, the two `+1`\'s miracly cancel each other! so we can simly write\n```\n~(0xFFFFFFEC^mask) == -20\n```\n\nTo sum up, since Python allows arbitary length for integers, we first use a mask `0xFFFFFFFF` to restrict the lengths. But then we lose information for negative numbers, so we use the magical formula `~(a^mask)` to convert the result to Python-interpretable form.\n\nHere is the complete code\n```\nclass Solution(object):\n    def getSum(self, a, b):\n        """\n        :type a: int\n        :type b: int\n        :rtype: int\n        """\n        mask = 0xffffffff\n        while b:\n\t\t    sum = (a^b) & mask\n\t\t\tcarry = ((a&b)<<1) & mask\n            a = sum\n\t\t\tb = carry\n\n\t\tif (a>>31) & 1: # If a is negative in 32 bits sense\n\t\t\treturn ~(a^mask)\n\t\treturn a\n```
[]