首页 / PYTHON / 不使用python中的“”运算符的两个整数之和

不使用python中的“”运算符的两个整数之和

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了不使用python中的“”运算符的两个整数之和，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2028字，纯文字阅读大概需要3分钟。

内容图文

需要一些帮助来理解leetcode 371的python解决方案.“两个整数之和”.我发现https://discuss.leetcode.com/topic/49900/python-solution/2是投票最多的python解决方案,但我有理解它的问题.

>如何理解“％MASK”的用法以及为什么“MASK = 0x100000000”？
>如何理解“?((％MIN_INT)^ MAX_INT)”？
>当总和超过MAX_INT时,函数会显示负值(例如getSum(2147483647,2)= -2147483647),是不是不正确？

class Solution(object):

    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MAX_INT = 0x7FFFFFFF
        MIN_INT = 0x80000000
        MASK = 0x100000000
        while b:
            a, b = (a ^ b) % MASK, ((a & b) << 1) % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT)

解决方法:

让我们忽略MASK,MAX_INT和MIN_INT一秒钟.

为什么这个黑魔法按位的东西有效？

计算工作的原因是因为(a ^ b)是“求和”a和b的位.回想一下,当位不同时,按位xor为1,当位相同时,xor为0.例如(其中D是十进制,B是二进制),20D == 10100B,9D = 1001B：

 10100
  1001
 -----
 11101

和11101B == 29D.

但是,如果你有一个携带的情况,它不能很好地工作.例如,考虑添加(按位xor)20D和20D.

10100
10100
-----
00000

哎呀. 20当然不等于0.输入(a& b)<< 1个学期.该术语代表每个职位的“随身携带”.在while循环的下一次迭代中,我们从前一个循环中添加进位.所以,如果我们使用之前的例子,我们得到： 

# First iteration (a is 20, b is 20)
10100 ^ 10100 == 00000 # makes a 0
(10100 & 10100) << 1 == 101000 # makes b 40

# Second iteration:
000000 ^ 101000 == 101000 # Makes a 40
(000000 & 101000) << 1 == 0000000 # Makes b 0

现在b为0,我们完成了,所以返回一个.该算法通常起作用,不仅适用于我概述的特定情况.正确性的证明留给读者作为练习;)

面具做什么？

所有掩码正在做的是确保值是一个整数,因为你的代码甚至有注释声明a,b和返回类型是int类型.因此,因为最大可能的int(32位)是2147483647.所以,如果你在这个值中添加2,就像在你的例子中那样,int溢出,你得到一个负值.你必须在Python中强制执行此操作,因为它不遵循其他强类型语言(如Java和C)定义的int边界.考虑以下：

def get_sum(a, b):
    while b:
        a, b = (a ^ b), (a & b) << 1
    return a

这是没有掩码的getSum版本.

print get_sum(2147483647, 2)

输出

2147483649

而

 print Solution().getSum(2147483647, 2)

输出

-2147483647

由于溢出.

故事的寓意是,如果将int类型定义为仅表示32位,则实现是正确的.

内容总结

以上是互联网集市为您收集整理的不使用python中的“”运算符的两个整数之和全部内容，希望文章能够帮你解决不使用python中的“”运算符的两个整数之和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/787755.html

来源：【匿名】