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

Question

Estaba buscando una manera 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 imaginar rápidamente una prueba matemática de por qué esto es correcto.
¿Alguien podría iluminarme?

Answer 1

A & amp; 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 activados en A. Agrega B a eso, y obtendrás todos los bits que están activados en A o los que están en B.

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

Answer 2

Imagine que tiene dos números binarios: a y 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 que satisfacen la condición anterior. En este caso, es fácil ver que a | b sería exactamente igual a a + b .

a | b = 11100111
a + b = 11100111

Ahora tomemos 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 lo mismo que a + b en este caso? No

a | b = 11100111
a + b = 11101011

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

Esto significa que la diferencia entre a | b y a + b ocurre 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 suman "dos veces". y producir un carry, que arruina la similitud entre a | b y a + b .

Ahora observe a & amp; b . ¿Qué significa a & amp; b calcular? a & amp; b produce el número que tiene 1 en todos los bits, donde tanto a como b tienen 1. En nuestro último ejemplo

a =     00100111
b =     11000100
a & b = 00000100

Como viste anteriormente, estos son exactamente los bits que hacen que a + b difiera de a | b . El 1 en a & amp; b indica todas las posiciones donde se llevará a cabo.

Ahora, cuando hacemos a - (a & amp; b) efectivamente eliminamos (restamos) todas " ofensivas " bits de a y solo esos bits

a - (a & b) = 00100011

Los números a - (a & amp; b) y b no tienen 1 bit común, lo que significa que si agregamos a - (a & amp; b ) y b no nos encontraremos con un carry, y, si lo piensas, deberíamos terminar con el mismo resultado que si hubiésemos hecho a | b

a - (a & b) + b = 11100111

Answer 3

A & amp; B = C donde los bits que quedan establecidos en C son aquellos establecidos en A y en B.
A-C = D o B-C = E establece solo estos bits comunes en 0. No hay ningún efecto de transporte porque 1-1 = 0.
D + B o E + A es similar a A + B, excepto que debido a que restamos A & amp; B anteriormente, no habrá carry debido a que se han borrado todos los bits establecidos comúnmente en D o E.

El resultado neto es que A-A & amp; B + B o B-A & amp; B + A es equivalente a A | B.

Aquí hay una tabla de verdad si aún es 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

Observe las filas de acarreo en las operaciones + y -, las evitamos porque A- (A & amp; B) establece casos en los que ambos bits en A y B son 1 a 0 en A, y luego agregarlos desde B también trae los otros casos fueron 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 & amp; B) + B son idénticas.

Otra forma de ver el globo ocular es ver que A + B es casi como A | B, excepto por el carry en la fila inferior. A & amp; B aísla esa fila inferior para nosotros, A-A & amp; B mueve esas casillas aisladas hacia arriba dos filas en la tabla +, y (A-A & amp; B) + B se convierte en equivalente a A | B.

Si bien podría conmutar esto a A + B- (A & amp; B), tenía miedo de un posible desbordamiento, pero parece injustificado:

#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

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

Answer 4