位操作

位操作高效解决问题

其中，
Sum of Two Integers
Use ^ and & to add two integers

int getSum(int a, int b) {
    return b==0? a:getSum(a^b, (a&b)<<1); //be careful about the terminating condition;
}

用^及& 实现 加法
看了好一会儿，才看懂
两个位串相加，结果可由两部分组成：不同的位 与 相同的位
不同的位，用^取得
相同的位，相加并进位，先&运算,再左移1位
此两部分相加，即得结果，递归下去即可。

注意边界情况，整型通常4字节32位，不断左移终使b为0，结束递归。
对于python/php等脚本语言，实现了非常大的整型范围，这样写法则不成了，需用mask限制32位

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)

如上，Python3整型是无界的(无限大)，想限定整型上限，如何能让其如C/Java一样表示补码？
为了理解最后一行代码的含义，我们可以假设场景，然后确定目的是什么。
假设C语言int占4位，python语言int占8位，mask为0xF
举例，我们得到的a若为 0b0101，它被预期正常解释，算法结束；若a为0b1011，根据此算法的隐含条件，我们想让它被解释成负数，就得让它符号扩展到 0b11111011

~(a ^ mask)

0b1011 => 0b0100 => 0b11111011