位操作

位操作高效解决问题

其中,
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

标签: none

添加新评论