誰かがこのleetcode解決法が負の数でどのように機能するか説明できますか？

Question

これはCalculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

はなぜMODとMAX_INTを必要とし、この部分は何をやっている、leetcode problem 371ためのソリューションですか？ ~(a & MAX_INT)^MAX_INT

def getSum(a, b): 
    """ 
    :type a: int 
    :type b: int 
    :rtype: int 
    """ 
    MOD  = 0xFFFFFFFF 
    MAX_INT = 0x7FFFFFFF 
    while b != 0: 
     a, b = (a^b) & MOD, ((a & b) << 1) & MOD 
    return a if a <= MAX_INT else ~(a & MAX_INT)^MAX_INT 

print getSum4(-4,2) 
-2 

溶液をthis blog

Answer 1

からMOD、MAX_INTと~(a & MAX_INT)^MAX_INT理由は32ビット整数をシミュレートすることです。これは、Pythonの整数が束縛されていないために必要です。

& MODは、結果の32ビット最下位ビットのみを保持するために使用されます。整数が32ビットのみのシステムでは、これは事実上起こります。余分なビットは単に落とされます。

MAX_INTの使用法は、32ビット整数の整数オーバーフローとなるものを適切に処理することです。 0x40000000と0x40000000を追加すると、0x80000000となり、Pythonでは正の整数に過ぎません。 32ビットの整数では、これはオーバーフローになり、その値は-0x80000000に等しくなります。

a & MAX_INTは、32ビット整数で基本的に符号として使用される最上位ビットを削除することです。 ~(...)^MAX_INTは、実際に使用されているビット数に31ビットの数値を拡張する方法です。たとえば、Pythonが42ビットしか使用しない場合、-0x80000000は0xff80000000と表されます。言い換えれば、最下位31ビットを超えてすべてのビットを1に設定するだけです。 （~xを実行することは、x^0xff...ffと同じです。したがって、~x^MAX_INTは、x^(0xff..ff MAX_INT)およびx^0xff...ff80000000と同じで、x | 0xff...ff80000000でも、xは31ビットのみを使用します）。

もちろん、Pythonは概念的には固定ビット数を使用していませんが、無限数のビットが1に設定されているかのように見ることができます。これらのビットは、正の数（例えば、0x00 ... 001）のすべての0ビットを格納しないのと同じように。

~x^MODの代わりに、32番目のビットが正しく設定されていることを使用します。

Answer 2

コードを理解しようとするのは苦労していますが、間違いなく問題なく動作しますが、最初からやり直すことをお勧めします。まず、数字のinteger representationと負の数字のtwo's complementをマスタービット演算子にしてください。それからちょうどテストのカップルとこれら2つのシンプルな機能を理解しよう：

def add_32bits_buggy(a, b): 
    MOD = 0xFFFFFFFF 

    while (a != 0): 
     c = (b & a) & MOD 
     b = (b^a) & MOD 
     a = (c << 1) & MOD 

    return b 


def add_32bits(a, b): 
    MOD = 0xFFFFFFFF 
    MAX_INT = 0x7FFFFFFF 

    while (a != 0): 
     c = (b & a) & MOD 
     b = (b^a) & MOD 
     a = (c << 1) & MOD 

    if b <= MAX_INT: 
     return b 
    else: 
     return ~(b & MAX_INT)^MAX_INT 

# value to test edge_cases 
max_v = 0xFFFFFFFF 

# Positive integers 
i = 1 
while i <= max_v: 
    i *= 2 
    a, b = max_v + 1, i 
    print "{0:10d}\t{1:10d}".format(
     add_32bits(a, b), add_32bits_buggy(a, b), 
    ) 

print '-'*80 

# Negative integers 
i = 1 
while i <= max_v: 
    i *= 2 
    a, b = max_v + 1, i 
    print "{0:10d}\t{1:10d}".format(
     add_32bits(a, -b), add_32bits_buggy(a, -b), 
    ) 

「我々はMODとMAX_INTを必要とし、この部分は何をやっているのはなぜ~(a & MAX_INT)^MAX_INT？」関数add_32bits_buggyは、あなたの質問にお答えします。 add_32bits（元のコードに相当）は、リターンのためにこれらのケースがどのように修正されたかを示します。

希望します。