Warum ist (a | b) entspricht a - (a & b) + b?

Question

Ich war auf der Suche nach einem Weg, um eine BITOR () mit einer Oracle-Datenbank und stieß auf einem Vorschlag zu tun, nur verwenden BITAND () statt, zu ersetzen BITOR (a, b) mit a + b - BITAND (a, b) .

Ich habe es getestet von Hand ein paar Mal und überprüft es scheint für alle binären Zahlen zu arbeiten, die ich denken konnte, aber ich kann schnell mathematischen Beweis nicht denken, warum dies richtig ist.
Könnte mir jemand aufklären?

Answer 1

A & B ist die Menge von Bits, die auf sowohl A und B. A - (A & B) läßt Dich mit all den Bits, die nur auf in A. sind B zu, dass hinzufügen, und Sie erhalten alle Bits, die auf in A oder diejenigen sind, die auf in B. sind

Einfache Zugabe von A und B wird nicht wegen des Tragens arbeiten, in dem sowohl ein 1 Bit haben. Durch das Entfernen Sie zuerst die Bits gemeinsam A und B, wissen wir, dass (A- (A & B)) wird mit B keine Bits gemeinsam haben, sie so Addition garantiert nicht einen Übertrag zu erzeugen.

Answer 2

Stellen Sie sich vor, Sie haben zwei Binärzahlen: a und b. Und lassen Sie sich sagt, dass diese Zahl noch nie 1 in der gleichen Bit zur gleichen Zeit, das heißt, wenn a 1 in einem gewissen Bit hat, hat der b immer 0 in dem entsprechenden Bit. Und in der anderen Richtung, wenn b 1 in einem gewissen Bit hat, a dann hat immer 0 in diesem Bit. Zum Beispiel

a = 00100011
b = 11000100

Dies wäre ein Beispiel für a und b Erfüllung der obigen Bedingung sein. In diesem Fall ist es einfach, dass a | b wäre genau die gleich wie a + b zu sehen.

a | b = 11100111
a + b = 11100111

Lassen Sie uns nun zwei Nummern, die unsere Bedingung verletzen, das heißt zwei Zahlen haben mindestens eine 1 in einem gemeinsamen Bit

a = 00100111
b = 11000100

ist die gleiche wie a | b in diesem Fall a + b? Nein

a | b = 11100111
a + b = 11101011

Warum sind sie anders? Sie sind anders, denn wenn wir das Bit +, die mit 1 in beiden Zahlen hat, produzieren wir so genannte tragen : das resultierende Bit 0 und 1 auf das nächste Bit nach links durchgeführt wird: 1 + 1 = 10. Der Betrieb | hat keinen Übertrag, so 1 | 1 ist wieder nur 1.

Das bedeutet, dass die Differenz zwischen a | b a + b und tritt auf, wenn und nur wenn die Zahlen mindestens eine 1-Bit gemeinsam haben. Wenn wir mit 1 gemeinsam Bits zwei Zahlen summieren, erhalten diese gemeinsamen Bits „zweimal“ hinzugefügt und einen Übertrag erzeugen, die die Ähnlichkeit zwischen a | b und a + b ruiniert.

Jetzt bei a & b aussehen. Was bedeutet berechnen a & b? a & b erzeugt die Zahl, die 1 in allen Bits hat, wo sowohl a und b 1. In unserem aktuellen Beispiel haben

a =     00100111
b =     11000100
a & b = 00000100

Wie Sie oben gesehen haben, das sind genau die Bits, die a + b unterscheiden sich von a | b machen. Die 1 in a & b zeigen alle Positionen, an denen carry auftreten wird.

Wenn wir jetzt a - (a & b) tun wir effektiv entfernen (subtrahieren) alle "anstößigen" Bits von a und nur solche Bits

a - (a & b) = 00100011

Numbers a - (a & b) und b haben keine gemeinsame 1-Bits, was bedeutet, dass, wenn wir a - (a & b) und b hinzufügen, werden wir nicht in einem Übertrags laufen, und wenn man darüber nachdenkt, sollten wir mit dem gleichen Ergebnis am Ende, als ob wir nur hat a | b

a - (a & b) + b = 11100111

Answer 3

A & B = C, wo irgendwelche Bits in C links eingestellt sind diejenigen gesetzt sowohl in A als auch in B.
Entweder A-C = D oder B-C = E setzt gerade diese gemeinsamen Bits auf 0. Es gibt keine tragende Wirkung, weil 1-1 = 0.
D + B oder E + A ist ähnlich wie A + B mit der Ausnahme, dass, weil wir subtrahierten A & B vorher wird es keine carry sein aufgrund all gemeinsam einstell- Bits in D oder E gelöscht zu haben.

Das Nettoergebnis ist, dass A-A & B + B oder B-A & B + A entspricht A |. B

Hier ist eine Wahrheitstabelle, wenn es immer noch verwirrend ist:

 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

Beachten Sie die Carry-Zeilen in den + und - Operationen, wir diejenigen zu vermeiden, weil A- (A & B) setzt Fälle wurden beiden Bits in A und B 1 auf 0 in A sind, dann Zugabe von ihnen von B zurück bringt auch in den anderen Fälle gab es eine 1 in entweder A oder B war aber nicht da, wo beide 0 hatte, so dass die OR Wahrheitstabelle und die A- (A & B) + Tabelle B Wahrheit identisch sind.

Ein andere Möglichkeit, es zu Augapfel ist, dass A zu sehen + B fast wie A ist | B mit Ausnahme des Übertrag in der unteren Reihe. A & B-Isolaten, dass untere Reihe für uns, A-A und B sind solche isoliert verrohrten bis zwei Reihen in der Tabelle bewegt +, und das (A-A & B) + B wird zu A äquivalent |. B

Während Sie dies auf A + B (A & B) pendeln konnten, hatte ich Angst vor einem möglichen Überlauf, aber das war nicht gerechtfertigt scheint es:

#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

Bearbeiten : Also schrieb ich diese vor dort Antworten waren, dann etwa 2 Stunden Ausfallzeit auf meinem Heim-Verbindung da war, und ich es endlich geschafft, es zu veröffentlichen, zu bemerken erst danach, dass es würde richtig beantwortet zweimal worden. Persönlich ziehe ich auf eine Wahrheitstabelle bezieht bitweise Operationen zu arbeiten, so dass ich es für den Fall, lassen Sie es jemand hilft.

Answer 4