（a | b）がa-（a＆amp; b）+ bと同等なのはなぜですか？
https://stackoverflow.com/questions/1604258
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
OracleデータベースでBITOR（）を実行する方法を探していましたが、BITTOR（a、b）を+ b-BITAND（a、b）に置き換えて、代わりにBITAND（）を使用するという提案に出くわしました。
数回手作業でテストし、考えられるすべての2進数で機能するように見えることを確認しましたが、これが正しい理由を簡単に数学的に証明することはできません。
誰かが私を啓発してもらえますか？
解決
A＆amp; Bは、AとBの両方でオンになっているビットのセットです。A-（A＆amp; B）は、Aでのみオンになっているすべてのビットを残します。それにBを追加すると、オンになっているすべてのビットを取得しますAまたはBでオンになっているもの。
AとBの単純な加算は、両方とも1ビットの場所にあるため、機能しません。 AとBに共通のビットを最初に削除することにより、（A-（A＆amp; B））がBと共通のビットを持たないことがわかるため、これらを一緒に加算しても桁上げが発生しないことが保証されます。
他のヒント
2つの2進数、 a と b があるとします。そして、これらの数値が同じビットに同時に1を持つことは決してないとしましょう。つまり、 a があるビットに1がある場合、 b は対応するビットに常に0を持ちます。 。また、別の方向では、 b のビットが1である場合、 a のビットは常に0です。例
a = 00100011
b = 11000100
これは、上記の条件を満たす a および b の例です。この場合、 a | b は a + b とまったく同じです。
a | b = 11100111
a + b = 11100111
今、私たちの条件に違反する2つの数字を取りましょう。つまり、2つの数字が少なくとも1つの共通ビットに1を持っています
a = 00100111
b = 11000100
は aです| b この場合 a + b と同じですか？いいえ
a | b = 11100111
a + b = 11101011
なぜ違うのですか？両方の数値に1が含まれるビットを + すると、いわゆる carry が生成されるため、結果のビットは0であり、1は次のビットに送られるため、これらは異なります。左側： 1 + 1 = 10 。操作 | にはキャリーがないため、 1 | 1 は再び1です。
これは、 a | b および a + b は、数字の共通ビットに少なくとも1つの1がある場合にのみ発生します。共通ビットが1の2つの数値を合計すると、これらの共通ビットは「2回」追加されます。キャリーを生成します。これにより、 a | b および a + b 。
a＆amp;を見てください。 b 。 a＆amp;とはb 計算しますか？ a＆amp; b は、 a と b の両方が1であるすべてのビットに1が含まれる数値を生成します。最新の例では
a = 00100111
b = 11000100
a & b = 00000100
上で見たように、これらは a + b が a | b 。 a＆amp;の1 b は、キャリーが発生するすべての位置を示します。
今、 a-（a＆amp; b）を実行すると、すべての＆quot; offending＆quot;を効果的に remove （減算）します。 a からのビットとそのようなビットのみ
a - (a & b) = 00100011
数字 a-（a＆amp; b）と b には共通の1ビットがないため、 a-（a＆amp; b ）および b キャリーは実行されません。考えてみると、 a |を実行した場合と同じ結果になります。 b
a - (a & b) + b = 11100111
A＆amp; B =C。Cに設定されたままのビットは、AとBの両方に設定されたビットです。
A-C = DまたはB-C = Eのいずれかで、これらの共通ビットのみが0に設定されます。1-1= 0のため、キャリング効果はありません。
D + BまたはE + AはA + Bと似ていますが、以前にA＆amp; Bを減算したため、DまたはEのすべての一般に設定されたビットをクリアしたためにキャリーがありません。
最終的な結果は、A-A＆amp; B + BまたはB-A＆amp; B + AはA | Bと同等です。
まだ混乱している場合の真理値表は次のとおりです。
A | B | OR A | B | & A | B | - A | B | + ---+---+---- ---+---+--- ---+---+--- ---+---+--- 0 | 0 | 0 0 | 0 | 0 0 | 0 | 0 0 | 0 | 0 0 | 1 | 1 0 | 1 | 0 0 | 1 | 0-1 0 | 1 | 1 1 | 0 | 1 1 | 0 | 0 1 | 0 | 1 1 | 0 | 1 1 | 1 | 1 1 | 1 | 1 1 | 1 | 0 1 | 1 | 1+1
+および-演算のキャリー行に注意してください。A-（A＆amp; B）セットの場合はAの両方のビットであり、AのBは1から0であるため、それらをBから追加すると、他のケースでは、AまたはBのいずれかに1があり、両方に0がなかったため、OR真理値表とA-（A＆amp; B）+ B真理値表は同一です。
別の目玉の方法は、下の行の桁上げを除いて、A + BがほぼA | Bに似ていることを確認することです。 A＆amp; Bはその最下行を分離し、A-A＆amp; Bは分離されたそれらを+テーブルの2行上に移動し、（A-A＆amp; B）+ BはA | Bと同等になります。
これをA + B-（A＆amp; B）に通勤させることはできましたが、オーバーフローの可能性を恐れていましたが、不当だったようです：
#include <stdio.h>
int main(){ unsigned int a=0xC0000000, b=0xA0000000;
printf("%x %x %x %x\n",a, b, a|b, a&b);
printf("%x %x %x %x\n",a+b, a-(a&b), a-(a&b)+b, a+b-(a&b)); }
c0000000 a0000000 e0000000 80000000
60000000 40000000 e0000000 e0000000
編集：だから答えが出る前にこれを書いたのですが、その後、自宅の接続で2時間ほどダウンタイムがあり、やっと投稿しました。 2回正しく回答されました。個人的には、ビットごとの演算を行うために真理値表を参照することを好むため、誰かを助ける場合に備えてそのままにしておきます。
