12 
public int add(int a, int b){  
        while (b != 0){
            int carry = (a & b) ;

            a = a ^ b; 

            b = carry << 1;
        }
        return a;
 }

これは、ビット演算を使用して 2 つの整数の和を計算するコードです。

手動/プログラムで計算すると、すべての整数に対して機能することがわかります。aしかし、との中間値の間の関係を理解することはできませんcarry。そして、なぜキャリーに2を掛けて割り当てるのbですか?

PS: ここで 1 つの答えを見つけました Bitwise Multiply and Add in Java です が、これは乗算用であり、加算用ではありません。

4

5 に答える 5

2

変数bとcarryは、余分な数字を「運ぶ」ために使用されます。たとえば、2 進数では1+1 = 10,10は 2 桁の数字です。1in10は左隣の桁に配置する必要があります。それwhile()が、プログラムでループが行うことです。1同じ場所に数字がある場合 ( a & b)は、 ( )carryの XOR に設定されます。これは、両方ではなくどちらか一方の値が 2 である場合にのみ、各桁に の値を与えます(2 進算術を実行する場合、まさにそれが起こります。つまり、2 つの が加算されるため、1 の位は になります)。その後、（または1つ左にシフト）が割り当てられますba ^ b1ab1+1 = 1010carry << 1carry*2carryb. aループは、との新しい値を使用して、がゼロになるbまで繰り返さbれます (これはcarry、ゼロでもあることを意味します)。

于 2013-06-27T11:45:19.600 に答える
2

ここにあるすべての数字を 2 進法で考えてみてください。

そのようなコードで通常見つけたいのは、「ループ不変条件」です。この場合、反復ごとに a + b が一定であることを確認したいと考えています。したがって、b が 0 になってループを抜ける場合、a は元の a と b の合計に等しくなければなりません。次のステップは、ループが最終的に終了することを確認することです。後でこれに戻ります。まず、この場合は等式を使用している不変部分を理解しましょう。

a + b = (a ^ b) + 2 * (a & b)

ループ内で、新しい a は古い a ^ b と等しくなり、新しい b は 2 * (a & b) になります。これは (a & b) << 1 と同じです。これが問題の本質です。この平等。それはまさにあなたが足し算をする方法です。

解決策を2つ紹介します。両方で、次の単純な事実を使用します。

x + y = x ^ y

x と y に共通のビットが設定されていないとき。

これを正式に確認する簡単な方法は、次のことに注意することです。

a + b = a + b - 2(a & b) + 2(a & b)
= (a - (a & b)) + (b - (a & b)) + 2(a & b)
= (a - (a & b)) ^ (b - (a & b)) + 2(a & b)
= (a ^ (a & b)) ^ (b ^ (a & b)) + 2(a & b)
= a ^ b + 2(a & b)

長いソリューションでは、次のように数学的帰納法を使用します (これはやり過ぎだと考える人もいるかもしれませんが、私のオプションでは、それを知る価値があります)。

最初に、a と b の両方が 0 の場合に機能することを確認します (このアルゴリズムがどのように機能するかを説明する 1 ビットの数値を試すこともできます)。数学的帰納法を使用するときは、この手順を忘れないでください。

次に、これが n-1 ビット数で機能すると仮定して、n ビット数でも機能することを示さなければなりません。ここで、a = 2a' + a'' = 2a' ^ a'' および b = 2b' + b'' = 2b' ^ b'' と記述します。ここで、a''、b'' はセット {0, 1} にあります (その場合、2a' と a'' には共通のビットが設定されていません!)。それで：

(a ^ b) + 2(a & b) = (2a' ^ a'' ^ 2b' ^ b'') + 2((2a'' ^ a') & (2b'' ^ b')) =
(2a' ^ 2b') ^ (a'' ^ b'') + 2((2a'' & 2b'') ^ (a'' & b'')) = 
(2a' ^ 2b') + (a'' ^ b'') + 2((2a'' & 2b'') + (a'' & b'')) =
(2a' ^ 2b') + 2((2a'' & 2b'') + (a'' ^ b'') + (a'' & b'')) =
2a' + 2b' + a'' + b'' = a + b

最後に確認することは、このループが実際に終了することです。これを確認するには、各ステップで a と b の両方が非負であり、これが各反復後も true のままであるという事実を使用します。

したがって、b <= a + b となります。次に、n ステップの後、b は n 個のゼロで終わらなければならないことに注意してください。したがって、b = 0 または b = k * 2* n >= 2 *n > 2**log_2(a+b) = a+b のいずれかが矛盾するため、log_2(a+b) ステップを超えることはできません。予測。ここで ** はもちろん累乗を表します。

Java では、このアルゴリズムは負の整数でも機能します。これは、負の整数が Java およびほとんどのプログラミング言語でどのように格納されるかによるものです。ここで、符号付き数値と符号なし数値の加算と減算はビットに対して同じように機能するため、符号なし数値で機能するコードは符号付きでも機能します。

于 2013-06-27T13:43:37.153 に答える
1

これは、1+1=10 (ビットごと) という事実に依存しています。つまり、「加算がキャリー ビットを意味する場合、合計電流の桁列はゼロでなければなりません」。「<<」演算子は、「int を 2 で乗算する」と考えるのではなく、「ビットを左に運ぶ」と考えてください。

コードの平凡な説明を次に示します。

carry = Ignore those bits that will produce carry bits (because their sum in the current "column"  will be 0), but collect the carry bits. 
a = Add those bits of a and b that won't produce a carry bit (i.e. use XOR)
b = Carry the carry bits one column left.
于 2013-06-27T12:08:22.107 に答える