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

Question

que estaba buscando una manera de hacer un BITOR() con una base de datos Oracle y me encontré con una sugerencia de usar sólo BITAND() BITOR lugar, en sustitución de (a, b) con a + b - BITAND (a, b).

he comprobado con la mano un par de veces y verificados parece que funciona para todos los números binarios que se me ocurrieron, pero no puedo pensar en voz rápida prueba matemática de por qué esto es correcto.
¿Podría alguien iluminarme?

Answer 1

A & B es el conjunto de bits que están en A y B. A - (A & B) te deja con todos esos bits que están solo en A. Añade B a eso, y obtienes todo los bits que están en en a o aquellos que están en en B.

adición simple de a y B no funcionará porque de llevar donde ambos tienen un 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 agregarlos juntos garantiza que no producirán un acarreo.

Answer 2

Imagine que tiene dos números binarios: a y b. Y digamos que estos números nunca tienen 1 en el mismo bit al mismo tiempo, es decir, si a tiene 1 en algún bit, el 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 

Esto sería un ejemplo de a y b que satisface la condición anteriormente. En este caso, es fácil ver que a | b sería exactamente igual a a + b.

a | b = 11100111 
a + b = 11100111 

Echemos dos números que violan nuestra condición, es decir, dos números tienen al menos un 1 en algunos poco comunes

a = 00100111 
b = 11000100 

Es 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 + la parte que tiene 1, tanto en número, se producen los llamados de transporte: el bit resultante es 0, 1 y se lleva a la siguiente bit a la izquierda: 1 + 1 = 10. Operación | no tiene transporte, por lo que es de nuevo sólo 1 | 1 1.

Esto significa que la diferencia entre a | b y a + b se produce cuando, y sólo cuando los números tienen al menos un 1 en el bit comunes. 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 y a + b.

Ahora mira a & b. ¿Qué calcula 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 difieren de a + ba | b. El 1 en a & b indica todas las posiciones donde se producirá el acarreo.

Ahora, cuando hacemos a - (a & b) que efectivamente eliminamos (restar) todos los bits "ofender" de a y sólo tales bits de

a - (a & b) = 00100011 

Números a - (a & b) y b no tienen 1 bits comunes, lo que significa que si añadimos a - (a & b) y b no vamos a correr en un acarreo, y, si se piensa en ello, debemos terminar con el mismo resultado que si que acabamos de hacer a | b

a - (a & b) + b = 11100111 

Answer 3

A & B = C donde los bits restantes configurados en C son los configurados en A y en B.
O AC = D o BC = E establece solo estos bits comunes en 0. No hay efecto de transporte porque 1 -1 = 0.
D + E + B o A es similar a A + B, excepto que debido restamos Un & B previamente no habrá de transporte debido a haber limpiado bits de todos fijados en común 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 todavía 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

Aviso las filas de llevar en los signos + y - las operaciones, que evite esos porque A- (A & B) establece los casos eran ambos bits en A y B son 1 a 0 en A, luego sumarlos de B también trae los otros casos donde hubo un 1 en A o B pero no en donde ambos tenían 0, entonces la tabla de verdad O y la A- (A & B) + B tabla de verdad son idénticos.

Otra forma de ver el globo es ver que A + B es casi como A | B, excepto por el acarreo en la fila inferior. A & B aísla esa fila inferior para nosotros, A-A & B mueve aquellos aislados encapsulados en dos filas en la tabla +, y el (A-A & B) + B pasa a ser equivalente a A | B.

Mientras que usted podría conmutar este a A + B- (A & B), tenía miedo de un posible desbordamiento, pero que era injustificada que parece:

#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 

Edición: Así que escribí esto antes hubo respuestas, luego hubo unas 2 horas de tiempo de inactividad en la conexión de mi casa, y finalmente logré publicarlo, notando solo después que se había respondido correctamente dos veces. Personalmente, prefiero referirme a una tabla de verdad para calcular operaciones bit a bit, así que lo dejo en caso de que ayude a alguien.

Answer 4