Perché (a | b) è equivalente a - (a & b) + b?

Question

Stavo cercando un modo per fare un BITOR() con un database Oracle e ho trovato un suggerimento per usare semplicemente BITAND() invece, sostituendo BITOR (a, b) con un + b - BITAND (a, b).

L'ho provato a mano alcune volte e ho verificato che sembra funzionare per tutti i numeri binari a cui potrei pensare, ma non riesco a pensare a una rapida dimostrazione matematica del perché questo è corretto.
Qualcuno potrebbe illuminarmi?

Answer 1

A & B è l'insieme di bit che si trovano su entrambi in A e B. A - (A & B) ti lascia con tutti i bit che sono solo su in A. Aggiungi B a questo, e si ottiene tutto i bit attivati ​​in A o quelli attivati ​​in B.

L'aggiunta semplice di A e B non funzionerà a causa del trasporto in cui entrambi hanno un 1 bit. Rimuovendo prima i bit comuni ad A e B, sappiamo che (A- (A & B)) non avranno bit in comune con B, quindi aggiungerli insieme è garantito non produrre un carry.

Answer 2

Immagina di avere due numeri binari: a e b. E diciamo che questi numeri non hanno mai 1 nello stesso bit allo stesso tempo, cioè se a ha 1 in qualche bit, lo b ha sempre 0 nel bit corrispondente. E in un'altra direzione, se b ha 1 in qualche bit, quindi a ha sempre 0 in quel bit. Ad esempio

a = 00100011 
b = 11000100 

Questo sarebbe un esempio di a e b soddisfano la condizione di cui sopra. In questo caso è facile vedere che a | b sarebbe esattamente lo stesso di a + b.

a | b = 11100111 
a + b = 11100111 

Vediamo ora due numeri che violano la nostra condizione, vale a dire due numeri hanno almeno un 1 in qualche po 'comune

a = 00100111 
b = 11000100 

È a | b lo stesso di a + b in questo caso? No

a | b = 11100111 
a + b = 11101011 

Perché sono diversi? Sono diversi perché quando abbiamo + il bit che ha 1 in entrambi i numeri, produciamo il cosiddetto trasportare: il bit risultante è 0 e 1 viene portato al bit successivo a sinistra: 1 + 1 = 10. Funzionamento | ha alcun riporto, quindi 1 | 1 è ancora solo 1.

Ciò significa che la differenza tra a | b e a + b verifica quando e solo quando i numeri hanno almeno un 1 nel bit comune. Quando sommiamo due numeri con 1 in bit comuni, questi bit comuni vengono aggiunti "due volte" e producono un carry, che rovina la similarità tra a | b e a + b.

Ora guardare a & b. Che cosa calcola a & b? a & b produce il numero che ha 1 in tutti i bit in cui sia a che b hanno 1.Nel nostro ultimo esempio

a =  00100111 
b =  11000100 
a & b = 00000100 

Come si è visto in precedenza, questi sono esattamente i bit che compongono a + b differiscono da a | b. Il numero 1 in a & b indica tutte le posizioni in cui si verificherà il trasporto.

Ora, quando facciamo a - (a & b) abbiamo effettivamente rimuovere (sottrazione) tutti "offendere" bit di a e solo quei bit

a - (a & b) = 00100011 

Numeri a - (a & b) e b hanno alcun incontrate 1 bit, il che significa che se aggiungiamo a - (a & b) e b noi non incorrere in un carry, e, se ci pensate bene, dovremmo finire con lo stesso risultato come se abbiamo appena fatto a | b

a - (a & b) + b = 11100111 

Answer 3

A & A B = C dove i bit lasciati impostati in C sono quelli impostati sia in A che in B.
O AC = D o BC = E imposta solo questi bit comuni su 0. Non c'è effetto di trasporto perché 1 -1 = 0.
D + B o E + A è simile ad A + B eccetto che, poiché abbiamo sottratto A & B precedentemente non ci sarà alcun riporto causa di aver rimosso tutta comunemente definiti bit in D o E.

Il risultato netto è che AA & B + B o BA & B + A è equivalente a A | B.

Ecco una tabella di verità se è ancora confusa:

 
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

Avviso le righe portare in + e - le operazioni, evitiamo quelli perché A- (A & B) stabilisce i casi sono stati entrambi i bit in A e B sono da 1 a 0 in A, quindi aggiungerli di nuovo da B porta negli altri casi se c'era un 1 in A o B ma non dove entrambi avevano 0, quindi la tabella di verità OR e A- (A & B) + La tabella di verità B è identica.

Un altro modo per eyeball è vedere che A + B è quasi come A | B ad eccezione del carry nella riga in basso. A & B isola quella riga inferiore per noi, A-A & B sposta quelli isolati racchiusi tra due righe nella tabella + e (A-A & B) + B diventa equivalente a A | B.

Mentre si potrebbe commutare ad un + B- (A & B), avevo paura di un possibile trabocco, ma che era ingiustificata sembra:

#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 

Edit: Così ho scritto questo prima c'erano delle risposte, poi ci sono state circa 2 ore di down time sulla mia connessione di casa, e finalmente sono riuscito a postarlo, notando solo dopo che era stato correttamente risposto due volte. Personalmente preferisco fare riferimento a una tabella di verità per elaborare operazioni bit a bit, quindi la lascio nel caso in cui aiuti qualcuno.

Answer 4