Perché (a | b) equivale a a - (a & amp; b) + b?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

< >