Pythonで "+"演算子を使用しない2つの整数の和

Question

leetcodeのpython解を理解するための助けが必要です。371. "Sum of Two Integers"。私は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) 

Answer 1

の第二のためにMASK、MAX_INTとMIN_INTを無視してみましょう。

なぜこの黒い魔法のビット単位の作業が機能しますか？

(a^b)はaとbのビットを「合計」しているためです。ビットごとのxorは、ビットが異なる場合は1、ビットが同じ場合は0であることを思い出してください。 （Dは小数であり、Bはバイナリである）、例えば、20D == 10100B、および9D = 1001B：

10100 
    1001 
----- 
11101 

および11101B == 29D。

しかし、キャリー付きのケースがあれば、うまく動作しません。たとえば、20Dと20Dのビットを加算することを検討してください。

10100 
10100 
----- 
00000 

20 + 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を返します。このアルゴリズムは、概説した特定のケースだけでなく、一般的に機能します。

マスクは何をするのですか？

すべてのマスクがやっているあなたのコードがさえa、b、および戻り値の型がタイプintである旨の意見を持っているため、値は、整数であることを確実にすることです。したがって、可能な限り最大int（32ビット）は2147483647です。したがって、この例で行ったように、この値に2を加算すると、intがオーバーフローし、負の値になります。これは、intという境界を、JavaやC++のような強く型付けされた他の言語が定義しているとはみなさないので、これをPythonで強制しなければなりません。以下を考慮してください：

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ビットのみを表すように定義すると、ストーリーのモラルは実装が正しいということです。