Pourquoi est-ce que (a | b) est équivalent à a - (a & amp; b) + b?

Question

Je recherchais un moyen de créer un BITOR () avec une base de données Oracle et suis tombé sur une suggestion consistant à utiliser simplement BITAND (), en remplaçant BITOR (a, b) par a + b - BITAND (a, b) .

Je l'ai testé à la main plusieurs fois et vérifié qu'il semble fonctionner pour tous les nombres binaires auxquels je pouvais penser, mais je ne peux pas trouver une preuve mathématique rapide pour expliquer pourquoi c'est correct.
Quelqu'un pourrait-il m'éclairer?

Answer 1

A & amp; B est l'ensemble des bits activés en A et B. A - (A & B) vous laisse avec tous les bits activés uniquement en A. Ajoutez B à cela et vous obtenez tous les bits activés. dans A ou ceux qui sont dans B.

La simple addition de A et B ne fonctionnera pas, car les deux ont un bit. En supprimant d’abord les bits communs à A et à B, nous savons que (A- (A & B)) n’aura pas de bits en commun avec B;

Answer 2

Imaginez que vous avez deux nombres binaires: a et b . Et disons que ces nombres n'ont jamais 1 dans le même bit en même temps, c'est-à-dire que si a a 1 dans un bit, le b a toujours 0 dans le bit correspondant . Et dans un autre sens, si b a 1 dans un bit, alors a a toujours 0 dans ce bit. Par exemple

a = 00100011
b = 11000100

Ce serait un exemple de a et de b satisfaisant la condition ci-dessus. Dans ce cas, il est facile de voir que a | b serait exactement identique à a + b .

a | b = 11100111
a + b = 11100111

Prenons maintenant deux nombres qui violent notre condition, c'est-à-dire que deux nombres ont au moins un 1 dans un bit commun

a = 00100111
b = 11000100

Est-ce que a | b identique à a + b dans ce cas? Non

a | b = 11100111
a + b = 11101011

Pourquoi sont-ils différents? Ils sont différents car lorsque nous + le bit qui a 1 dans les deux nombres, nous produisons ce que nous appelons carry : le bit résultant est 0, et 1 est transféré au bit suivant. à gauche: 1 + 1 = 10 . L'opération | n'a pas de retenue, donc 1 | 1 est à nouveau juste 1.

Cela signifie que la différence entre a | b et a + b se produisent uniquement lorsque les nombres ont au moins un bit commun. Lorsque nous additionnons deux nombres avec 1 en bits communs, ces bits communs sont ajoutés "deux fois". et produire un report, ce qui ruine la similitude entre a | b et a + b .

Maintenant, regardons un & amp; b . Qu'est-ce que a & amp; b calculer? a & amp; b produit le nombre qui a 1 dans tous les bits où a et b ont 1. Dans notre dernier exemple

a =     00100111
b =     11000100
a & b = 00000100

Comme vous l'avez vu ci-dessus, ce sont exactement les bits qui différencient a + b de a | b . Le 1 dans a & amp; b indique toutes les positions où se produira le report.

Désormais, lorsque nous faisons a - (a & amp; b) , nous supprimons (soustrayez) tous les "fautifs". bits de a et uniquement de tels bits

a - (a & b) = 00100011

Les nombres a - (a & amp; b) et b n'ont pas de 1 bit commun, ce qui signifie que si nous ajoutons a - (a & amp; b ) et b nous ne rencontrerons pas de report, et si vous y réfléchissez, vous devriez obtenir le même résultat que si nous venions de faire a | b

a - (a & b) + b = 11100111

Answer 3

A & B = C où les bits restants définis dans C sont ceux définis dans A et dans B.
A-C = D ou B-C = E ne fait que mettre ces bits communs à 0. Il n'y a pas d'effet de portage car 1-1 = 0.
D + B ou E + A est similaire à A + B, sauf que, comme nous avons soustrait A & B précédemment, il n'y aura pas de report, car tous les bits définis dans D ou E ont été effacés.

Le résultat net est que A-A & B + B ou B-A & B + A est équivalent à A | B.

Voici une table de vérité si cela reste confus:

 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

Notez les lignes de retenue dans les opérations + et -, nous les évitons car A- (A & B) définit les cas où les deux bits dans A et B sont compris entre 1 et 0 dans A, puis les rajouter depuis B amène également les autres cas étaient un 1 dans A ou B mais pas dans les deux cas où il y avait 0, donc la table de vérité OR et la table de vérité A- (A & B) + B sont identiques.

Une autre façon de voir les choses est de voir que A + B est presque comme A | B, à l’exception du report dans la rangée du bas. A & B isole cette rangée inférieure pour nous, A-A & B déplace les deux rangées isolées dans la table +, et le (A-A & B) + B devient équivalent à A | B.

Bien que vous puissiez commuter ceci en A + B- (A & B), j’avais peur d’un débordement possible, mais c’était injustifié, il semble:

#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

Modifier : J'ai donc écrit ceci avant qu'il y ait des réponses, puis il y a eu environ 2 heures de temps d'inactivité sur ma connexion à la maison et j'ai finalement réussi à la publier, remarquant seulement après été correctement répondu deux fois. Personnellement, je préfère me référer à une table de vérité pour effectuer des opérations au niveau des bits, donc je la laisse au cas où cela aiderait quelqu'un.

Answer 4