Porque é que (a | b) equivalente a um - (a & b) + b?

Question

Eu estava procurando uma maneira de fazer uma BITOR () com um banco de dados Oracle e me deparei com uma sugestão para utilização apenas BITAND () em vez, substituindo BITOR (a, b), com a + b - BITAND (a, b) .

Eu testei-o com a mão algumas vezes e verificou que parece funcionar para todos os números binários que eu poderia pensar, mas eu não posso pensar em uma prova rápida matemática de por que isso está correto.
Alguém poderia me esclarecer?

Answer 1

A & B é o conjunto de bits que estão no em ambos A e B. A - (A & B) deixa-o com todos os bits que são apenas em em A. Add B a isso, e você terá toda a bits que estão no em a ou aqueles que estão em em B.

simples adição de A e B não vai funcionar porque de transportar onde ambos têm um 1 bit. Removendo o comum bits para A e B em primeiro lugar, sabemos que (A- (A & B)) não terá pedaços em comum com B, então juntá-las é a garantia de não produzir um carry.

Answer 2

Imagine que você tem dois números binários: a e b. E vamos dizer que esses números nunca tem 1 no mesmo bit, ao mesmo tempo, ou seja, se a tem 1 em algum bit, o b tem sempre 0 no bit correspondente. E em outra direção, se b tem 1 em algum pouco, então a tem sempre 0 em que pouco. Por exemplo

a = 00100011
b = 11000100

Este seria um exemplo de a e b satisfazer a condição acima. Neste caso, é fácil ver que a | b seria exatamente o mesmo que a + b.

a | b = 11100111
a + b = 11100111

Vamos agora dar dois números que violem a nossa condição, ou seja, dois números têm pelo menos um 1 em alguns pouco comum

a = 00100111
b = 11000100

é a | b o mesmo que a + b neste caso? Não

a | b = 11100111
a + b = 11101011

Por que são diferentes? Eles são diferentes porque quando nós + o pouco que tem 1 em ambos os números, nós produzimos chamado carry : o bit resultante é 0 e 1 é transportada para o próximo bit para a esquerda: 1 + 1 = 10. | operação não tem transporte, assim 1 | 1 é novamente apenas 1.

Isso significa que a diferença entre a | b e a + b ocorre quando e apenas quando os números têm pelo menos um 1 no bit comum. Quando se soma dois números com 1 em bits comuns, esses bits comuns são adicionados "duas vezes" e produzir um carry, que ruínas a semelhança entre a | b e a + b.

Agora olhe para a & b. O que faz a & b calcular? a & b produz o número que tem 1 em todos os bits onde ambos a e b têm 1. No nosso exemplo mais recente

a =     00100111
b =     11000100
a & b = 00000100

Como você viu acima, estes são exatamente os bits que formam a + b diferem de a | b. O 1 em a & b indicam todas as posições onde carry irá ocorrer.

Agora, quando fazemos a - (a & b) nós efetivamente remover (subtrair) todos "ofender" pedaços de a e apenas esses pedaços

a - (a & b) = 00100011

Números a - (a & b) e b não têm bits 1 comuns, o que significa que, se somarmos a - (a & b) e b que não vai correr em um carry, e, se você pensar sobre isso, devemos acabar com o mesmo resultado como se nós apenas fiz a | b

a - (a & b) + b = 11100111

Answer 3

A & B = C, onde os bits de esquerda definido em C são aqueles set em ambos A e B.
Ou A-C = D ou B-C = E define apenas a estes bits comuns para 0. Não há nenhum efeito de transporte, porque 1-1 = 0.
D + B ou E + A é semelhante ao de A + B, excepto que, porque subtraído A e B, anteriormente, não haverá nenhum transporte devido a ter apagada todos os bits normalmente fixados em D ou E.

O resultado líquido é que A-A & B + B ou B-A & B + A é equivalente a A |. B

Aqui está uma tabela de verdade, se ele ainda está 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 as linhas levar no + e - operações, evitar aqueles porque A- (A & B) casos conjuntos eram ambos os bits em A e B são 1 a 0 em A, em seguida, adicioná-los de volta de B também traz outro casos foram havia um 1 em a ou B, mas não em ambos tinha 0, de modo que a tabela de verdade oU e o A- (a & B) + tabela B verdade são idênticos.

Outra forma de globo ocular é ver que A + B é quase como um | B exceto para o transporte na linha de fundo. A & B isola essa linha de fundo para nós, A-A & B move esses isolados encaixotado até duas linhas na tabela +, eo (A-A & B) + B torna-se equivalente a A |. B

Enquanto você poderia comutar isso para A + B- (A & B), eu estava com medo de um possível estouro, mas que era injustificada 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

Editar : Então eu escrevi isso antes havia respostas, em seguida, houve cerca de 2 horas de tempo para baixo em minha conexão casa, e eu finalmente conseguiu publicá-la, notando só depois que ele tinha foram devidamente respondidas duas vezes. Pessoalmente eu prefiro referindo-se a uma tabela de verdade para trabalhar operações bit a bit, por isso vou deixá-lo em caso de ajuda de alguém.

Answer 4