美文网首页随笔
Leetcode 371. 两整数之和

Leetcode 371. 两整数之和

作者: zhipingChen | 来源:发表于2019-10-13 18:22 被阅读0次

    题目描述

    不使用运算符 + 和 - ​​​​​​​,计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

    示例 1:

    输入: a = 1, b = 2
    输出: 3

    示例 2:

    输入: a = -2, b = 3
    输出: 1

    解法

    之前在Leetcode 137. 只出现一次的数字 II中提到过二进制的异或运算相当于不进位加法,二进制的与运算相当于捕获进位点。则两整数相加,等同于两整数异或运算的值,加上与运算左移一位的值,迭代执行,直到进位点为零。所以该题目可以通过异或运算和与运算替代加法的执行。

    因为在python中整数不会溢出,所以要模拟32位二进制的位运算,需要每次运算后对mask=0x100000000执行取余运算,来获取后32位二进制。

    并且需要注意,32位二进制能够表示的最大数是max_int=0x7fffffff,即首位符号位为0。所以最后python表示的返回值,若大于max_int,则需要将该python返回值处理成与后32位二进制表示值相等的结果。

    因为此时python值大于max_int值,所以从右向左的第32位二进制位1,也就是32位二进制下的负数,此时需要做的处理操作,就是把第32位和左边的所有位(不确定python是多少位)都处理成1,也就是把32位二进制的下的负数,变成python下的负数。

    参考LeetCode上的一种处理方式,对0~31位进行取反,然后对所有位进行取反,以此完成32位及之后的所有位置1的操作。

    class Solution:
        def getSum(self, a: int, b: int) -> int:
            mask=0x100000000
            max_int=0x7fffffff
            min_int=0x80000000
            while b:
                a,b=(a^b)%mask,((a&b)<<1)%mask
            return a if a<=max_int else ~((a%min_int)^max_int)
    

    参考
    位运算详解以及在 Python 中需要的特殊处理

    相关文章

      网友评论

        本文标题:Leetcode 371. 两整数之和

        本文链接:https://www.haomeiwen.com/subject/zzkkmctx.html