在python中不使用「+」運算符的兩個整數之和

需要一些幫助來理解leetcode 371的python解決方案。「兩個整數的和」。我發現https://discuss.leetcode.com/topic/49900/python-solution/2是最多投票的Python解決方案，但我有問題了解它。在python中不使用「+」運算符的兩個整數之和

如何理解「％MASK」的用法以及爲什麼「MASK = 0x100000000」？
如何理解「〜（（a 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)

來源

2016-07-24 user1269298

這裏有什麼規定？只能使用按位運算符和'％'？ – mwm314

在按位運算符中使用'％'運算符實現加法有點荒謬。 – chepner

@ mwm314是的，這是正確的。更新了標題。 – user1269298

讓我們忽視了第二的MASK，MAX_INT和MIN_INT。

爲什麼這個黑魔法按位填充工作？

計算工作原因是因爲(a^b)是「求和」a和b的位。回想一下，當位不同時，異或是1，當位相同時0。例如（其中d是十進制和B是二進制），20D == 10100B，和9D = 1001B：

和11101B == 29D。

但是，如果您有攜帶的情況下，它不能很好地工作。例如，考慮添加（按位異或）20D和20D。

糟糕。 20 + 20肯定不等於0.輸入(a & b) << 1的術語。這個術語代表每個位置的「carry」。在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。該算法通常適用於所有特定情況，而不僅限於我所概述的具體情況。正確性的證明留給讀者作爲練習;）

面具做什麼？

所有屏蔽做的是確保該值是一個整數，因爲你的代碼，甚至有評論指出a，b，並返回類型爲int類型。因此，由於最大可能的int（32位）爲2147483647.因此，如果您將此值加2，就像您在示例中所做的那樣，則int溢出並且您得到負值。你必須用Python強制它，因爲它不尊重其他強類型語言如Java和C++定義的邊界。考慮以下內容：

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位，則故事的寓意是實現是正確的。

來源

2016-07-25 01:24:13 mwm314

在python中不使用「+」運算符的兩個整數之和

回答

相關問題