Perché (a | b) equivale a a - (a & amp; b) + b?
-
05-07-2019 - |
Domanda
Stavo cercando un modo per fare un BITOR () con un database Oracle e ho trovato un suggerimento per usare BITAND () invece, sostituendo BITOR (a, b) con a + b - BITAND (a, b) .
L'ho provato a mano alcune volte e ho verificato che sembra funzionare per tutti i numeri binari che mi vengono in mente, ma non riesco a trovare una rapida prova matematica del perché sia ??corretto.
Qualcuno potrebbe illuminarmi?
Soluzione
A & amp; B è l'insieme di bit che sono attivi sia in A che in B. A - (A & B;) ti lascia con tutti quei bit che sono solo in A. Aggiungi B a quello e ottieni tutti i bit che sono attivi in A o quelli che sono in B.
La semplice aggiunta di A e B non funzionerà a causa del trasporto in cui entrambi hanno 1 bit. Rimuovendo prima i bit comuni ad A e B, sappiamo che (A- (A & amp; B)) non avrà bit in comune con B, quindi sommarli è garantito per non produrre un carry.
Altri suggerimenti
Immagina di avere due numeri binari: a
e b
. E diciamo che questi numeri non hanno mai 1 nello stesso bit contemporaneamente, cioè se a
ha 1 in qualche bit, b
ha sempre 0 nel bit corrispondente . E in un'altra direzione, se b
ha 1 in qualche bit, allora a
ha sempre 0 in quel bit. Ad esempio
a = 00100011
b = 11000100
Questo sarebbe un esempio di a
e b
che soddisfano la suddetta condizione. In questo caso è facile vedere che a | b
sarebbe esattamente uguale a a + b
.
a | b = 11100111
a + b = 11100111
Ora prendiamo due numeri che violano la nostra condizione, ovvero due numeri hanno almeno un 1 in un bit comune
a = 00100111
b = 11000100
è un | b
uguale a a + b
in questo caso? Nessun
a | b = 11100111
a + b = 11101011
Perché sono diversi? Sono diversi perché quando +
il bit che ha 1 in entrambi i numeri, produciamo il cosiddetto carry : il bit risultante è 0 e 1 viene portato al bit successivo a sinistra: 1 + 1 = 10
. L'operazione |
non ha carry, quindi 1 | 1
è di nuovo solo 1.
Ciò significa che la differenza tra a | b
e a + b
si verificano quando e solo quando i numeri hanno almeno 1 in bit comune. Quando sommiamo due numeri con 1 in bit comuni, questi bit comuni vengono aggiunti "due volte". e produce un carry, che rovina la somiglianza tra a | b
e a + b
.
Ora guarda a & amp; b
. Cosa significa a & amp; b
calcola? a & amp; 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 hai visto sopra, questi sono esattamente i bit che rendono a + b
diverso da a | b
. Il 1 in a & amp; b
indica tutte le posizioni in cui si verificherà il carry.
Ora, quando facciamo a - (a & amp; b)
effettivamente rimuoviamo (sottraiamo) tutto " offendendo " bit da a
e solo tali bit
a - (a & b) = 00100011
I numeri a - (a & amp; b)
e b
non hanno 1 bit comune, il che significa che se aggiungiamo a - (a & amp; b )
e b
non ci imbatteremo in un carry e, se ci pensate, dovremmo finire con lo stesso risultato che se avessimo appena a | b
a - (a & b) + b = 11100111
A & amp; B = C dove tutti i bit lasciati impostati in C sono quelli impostati sia in A che in B.
A-C = D o B-C = E imposta solo questi bit comuni su 0. Non c'è alcun effetto portante perché 1-1 = 0.
D + B o E + A è simile ad A + B, tranne per il fatto che in precedenza abbiamo sottratto A & B; non ci sarà alcun carry a causa della cancellazione di tutti i bit comunemente impostati in D o E.
Il risultato netto è che A-A & B + B o B-A & amp; 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
Nota le righe di carry nelle operazioni + e -, evitiamo quelle perché A- (A & amp; B) imposta i casi in cui entrambi i bit in A e B sono da 1 a 0 in A, quindi aggiungendoli di nuovo da B porta anche negli altri casi c'era un 1 in A o B ma non dove entrambi avevano 0, quindi la tabella di verità OR e la tabella di verità A- (A & amp; B) + B sono identiche.
Un altro modo per osservare gli occhi è vedere che A + B è quasi come A | B tranne che per il carry nella riga in basso. A & amp; B isola quella riga inferiore per noi, A-A & B sposta quelle isolate racchiuse in due righe nella tabella +, e (A-A & amp; B) + B diventa equivalente a A | B.
Mentre potevi spostarlo in A + B- (A & amp; B), avevo paura di un possibile trabocco, ma che era ingiustificato 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
Modifica : così ho scritto questo prima che ci fossero delle risposte, poi ci sono state 2 ore di inattività sulla mia connessione di casa e sono finalmente riuscito a pubblicarlo, notando solo in seguito che avrebbe ricevuto una risposta corretta due volte. Personalmente preferisco fare riferimento a una tabella di verità per elaborare operazioni bit per bit, quindi la lascerò nel caso in cui aiuti qualcuno.
< >