oracle - ¿Por qué es(a | b) equivalente a a-(a & b)+b?

binary computer-science

Question

Estaba buscando una forma de hacer un BITOR () con una base de datos Oracle y encontré una sugerencia para usar BITAND () en su lugar, reemplazando BITOR (a, b) con a + b - BITAND (a, b).

Lo probé con la mano varias veces y verifiqué que parece funcionar para todos los números binarios en los que podría pensar, pero no puedo pensar en una prueba matemática rápida de por qué esto es correcto.
¿Podría alguien iluminarme?

Answer 1

A y B es el conjunto de bits que están activados tanto en A como en B. A - (A y B) te deja con todos esos bits que están solo en A. Agrega B a eso, y obtendrás todos los bits que están en A o los que están en B.

La simple adición de A y B no funcionará debido a que los dos tienen 1 bit. Al eliminar primero los bits comunes a A y B, sabemos que (A- (A&B)) no tendrá bits en común con B, por lo que se garantiza que sumarlos no producirá un carry.

Answer 2

A&B = C donde todos los bits dejados establecidos en C son aquellos establecidos tanto en A como en B.
O bien AC = D o BC = E establece solo estos bits comunes en 0. No hay efecto de acarreo porque 1-1 = 0.
D + B o E + A es similar a A + B, excepto porque al restar A&B anteriormente no habrá acarreo debido a que se borraron todos los bits establecidos comúnmente en D o E.

El resultado neto es que AA & B + B o BA & B + A es equivalente a A | B.

Aquí hay una tabla de verdad si aún es confuso:

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

Observe las filas de acarreo en las operaciones + y -, las evitamos porque A- (A&B) establece que los casos en los que los bits en A y B son 1 a 0 en A, y luego agregarlos desde B también trae los otros casos que existieron fue un 1 en A o B, pero no donde ambos tenían 0, por lo que la tabla de verdad OR y la tabla de verdad A- (A&B) + B son idénticas.

Otra forma de ver el globo ocular es ver que A + B es casi como A | B, excepto el acarreo en la fila inferior. A&B aísla esa fila inferior para nosotros, AA&B mueve esas filas aisladas en la tabla +, y el (AA&B) + B se convierte en equivalente a A | B.

Si bien podría conmutar esto a A + B- (A&B), temía un posible desbordamiento, pero parece que eso no estaba justificado:

#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 : Así que escribí esto antes de que hubiera respuestas, luego hubo 2 horas de tiempo de inactividad en mi conexión doméstica, y finalmente logré publicarlo, solo después noté que había sido contestada correctamente dos veces. Personalmente, prefiero referirme a una tabla de verdad para elaborar operaciones de bit a bit, así que lo dejaré en caso de que ayude a alguien.

Answer 3

Imagina que tienes dos números binarios: b . Y digamos que este número nunca tiene 1 en el mismo bit al mismo tiempo, es decir, si a tiene 1 en algún bit, b siempre tiene 0 en el bit correspondiente. Y en otra dirección, si b tiene 1 en algún bit, entonces a siempre tiene 0 en ese bit. Por ejemplo

a = 00100011
b = 11000100

Este sería un ejemplo de a y b satisfacen la condición anterior. En este caso es fácil ver que a | b a | b sería exactamente lo mismo que a + b .

a | b = 11100111
a + b = 11100111

Tomemos ahora dos números que violan nuestra condición, es decir, dos números tienen al menos un 1 en algún bit común

a = 00100111
b = 11000100

Es a | b a | b lo mismo que a + b en este caso? No

a | b = 11100111
a + b = 11101011

¿Por qué son diferentes? Son diferentes porque cuando nosotros + el bit que tiene 1 en ambos números, producimos el llamado acarreo : el bit resultante es 0, y 1 se lleva al siguiente bit a la izquierda: 1 + 1 = 10 . Operacion | no tiene acarreo, entonces 1 | 1 1 | 1 es de nuevo solo 1.

Esto significa que la diferencia entre a | b a | b y a + b ocurren cuando y solo cuando los números tienen al menos un 1 en bit común. Cuando sumamos dos números con 1 en bits comunes, estos bits comunes se agregan "dos veces" y producen un acarreo, lo que arruina la similitud entre a | b a | b y a + b .

Ahora mira a a & b . ¿Qué calcula a a & b ? a & b produce el número que tiene 1 en todos los bits donde a y b tienen 1. En nuestro último ejemplo

a =     00100111
b =     11000100
a & b = 00000100

Como se vio anteriormente, estos son exactamente los bits que hacen que a + b difiera de a | b a | b . El 1 en a & b indica todas las posiciones donde ocurrirá el acarreo.

Ahora, cuando hacemos a - (a & b) eliminamos (restamos) todos los bits "ofensivos" de a y solo esos bits

a - (a & b) = 00100011

Los números a - (a & b) y b no tienen 1 bit común, lo que significa que si agregamos a - (a & b) b no nos encontraremos con un carry, y, si lo piensas, deberíamos terminamos con el mismo resultado como si acabáramos de hacer a | b a | b

a - (a & b) + b = 11100111