2つの整数をビット操作で追加します。

Question

+記号を使用して2つの整数を加算しようとしています。キャリーなしの合計はa^bとして計算でき、キャリーは（& b）< <として計算できます。1. 0x7FFFFFFFは32ビット整数の最大数ですが、マスクは何をするのですか？なぜキャリーとは、各繰り返しでMASKを使ってmodにする必要がありますか？結果がMAX_INTより大きい場合、〜（（& MAX_INT）^ MAX_INT）は何をしますか？

def get_sum(a,b): 
    MAX_INT = 0x7FFFFFFF 
    MASK = 0x100000000 
    while b: 
     carry = ((a&b) << 1) % MASK 
     a = (a^b) % MASK 
     b = carry 

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

Answer 1

のバイナリ101で、バイナリ1101、およびb = 5で、a = 13を考えてみましょう。

特に、Whileブロックで何が起こっているかを段階的に調べてみましょうが、今のところは% MASKの操作を無視してみましょう。

     carry= a= b= 
    a  b a&b  <<1 a^b carry 
    1101 101 101 1010 1000 1010 
    1000 1010 1000 10000 0010 10000 
    0010 10000  0  0 10010  0 
    10010  0 -> exit loop 

は18小数とMAX_INTより従って少ない=バイナリ10010ので、18は、（正しい）結果として返されます。

マスク操作の目的は、数値が大きくなると可能なMSBへのオーバーフローが発生しないようにすることです。

上記と同じ方法でElseの部分を把握できると思いますか？