(a | b)가 a - (a & b) + b와 같은 이유는 무엇입니까?

Question

오라클 데이터베이스에서 BITOR()를 수행하는 방법을 찾고 대신 BITOR (a, b)를 + b - BITAND (a, b)로 바꾸고 대신 BITAND()를 사용하라는 제안을 보았습니다.

몇 번 손으로 테스트 해 보았습니다. 생각할 수있는 모든 이진수에 대해 작동하는 것으로 확인되었지만 이것이 왜 올바른지 빠른 수학적 증명을 생각할 수는 없습니다.
누군가 나에게 계몽 수 있습니까?

Answer 1

& B는 A와 B 모두에있는 비트 집합입니다. A - (A & B)는 A에만있는 모든 비트를 남겨 둡니다. B를 추가하면 모든 A에있는 비트 또는 B에있는 비트입니다.

A와 B의 단순한 추가는 둘 다 1 비트를 가지고 있기 때문에 작동하지 않습니다. 처음에 A와 B에 공통 인 비트를 제거함으로써 (A- (A-& B))는 B와 공통된 비트를 가지지 않으므로 이들을 함께 더하면 캐리가 생성되지 않는다는 것을 알 수 있습니다.

Answer 2

두 개의 이진수 (a 및 b)가 있다고 가정 해보십시오. 그리고이 숫자가 동시에 같은 비트에서 1을 가질 수 없다고 가정하십시오. 즉, a에 비트가 1 인 경우 b은 항상 해당 비트에 0을가집니다. 그리고 다른 방향으로, 어떤 비트에 b이 1이면, a은 항상 그 비트에 0을가집니다. 예

a = 00100011 
b = 11000100 

내용이 a 및 b가 상기 조건을 만족하는 예 것이다. 이 경우 a | b은 정확히 a + b과 같을 것입니다.

a | b = 11100111 
a + b = 11100111 

의 지금 우리의 조건을 위반하는 두 숫자를 보자

, 즉 두 개의 숫자가 몇 가지 일반적인 비트

a = 00100111 
b = 11000100 

가 a | b이 경우 a + b와 같은 적어도 하나의 일이? 아니요

a | b = 11100111 
a + b = 11101011 

왜 다른가요? 그들은 우리가 + 두 숫자에 1을 가지고있는 비트를 가지고있을 때 을 수행하고을 수행하면 결과 비트가 0이되고 1은 왼쪽의 다음 비트 인 1 + 1 = 10으로 옮겨지기 때문에 그들은 다릅니다. 동작 |은 캐리가없는, 그래서 1 | 1 다시 인 숫자 공통 비트의 적어도 하나의 1이 될 때 단지 1

이 a | ba + b와의 차이가 때에 만 발생하는 것을 의미한다. 공통 비트가 1 인 두 개의 숫자를 합하면이 공통 비트가 "두 번"더해져 캐리가 생겨서 a | b과 a + b 사이의 유사성이 사라집니다.

이제 a & b을 확인하십시오. a & b는 무엇을 계산합니까? a & b은 a과 b이 모두 1 인 모든 비트에서 1을 갖는 숫자를 생성합니다.최신의 예에서

a =  00100111 
b =  11000100 
a & b = 00000100 

위에서 보았 듯이,이 정확히 a + b가 a | b 다를 구성하는 비트입니다. a & b의 1은 캐리가 발생할 모든 위치를 나타냅니다. 우리가 a - (a & b)을 수행 할 때 이제

, 우리는 효과적으로 제거 (빼기) 경우 있음을 의미 모든 "잘못된"a에서 비트와 그러한 비트

a - (a & b) = 00100011 

숫자 a - (a & b) 및 b가 공통 1 비트가 없다, 당신이 그것에 대해 생각한다면, 우리는 우리가 a | b

a - (a & b) + b = 11100111 

0,123,516했던 것과 동일한 결과와 끝까지해야한다, 우리는 a - (a & b) 추가 b 우리는 캐리로 실행되지 않으며,

Answer 3

& B = C 여기서 C에 설정된 왼쪽 비트는 A와 B 모두에 설정된 비트입니다.
AC = D 또는 BC = E는 이러한 공통 비트를 0으로 설정합니다. 1 -1 = 0. 우리 인해 D 또는 E.

최종 결과는 모든 공통 세트 비트를 클리어하는 데에 & B 이전에 캐리가 없을 것 감산 때문에
D의 +의 B 또는 E + A는 것을 제외하고는 A + B 비슷 AA & B + B 또는 BA & B + A는 A | B와 같습니다. 여전히 혼란 경우 여기

는 진리표이다 :

 
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

공지 사항 +와의 캐리 행 - A- (A & B)를 설정하기 때문에 작업, 우리는 사람들을 피 례 A의 두 비트와 B는 A에서 1 ~ 0이고, B에서 다시 추가하면 A 나 B 중 하나에 1이 있었지만 둘 다 0이 아닌 다른 경우가 발생하므로 OR 진리표와 A- (A & B) + B 진리표는 동일합니다.

안구를 보는 또 다른 방법은 A + B가 맨 아래 줄에있는 캐리를 제외하고 A | B와 거의 비슷하다는 것을 보는 것입니다. A & B는 우리를 위해 맨 아래 줄을 분리하고, A-A & B는 + 테이블에서 두 줄을 뒤집은 것을 이동시키고 (A-A & B) + B는 A | B와 동일하게됩니다. 당신은 A + B- (A & B)이 통근 수 있지만

, 나는 가능한 오버 플로우 두려워하지만 보인다 정당화했다 :

#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 

편집 : 그래서 내가 전에 쓴 대답이 있었다면, 집에 2 시간 정도의 시간이 걸렸습니다. 그리고 나는 마침내 그것을 게시 할 수있었습니다. 이후에는 제대로 답변을 받았음을 알았습니다. 개인적으로는 비트 연산을 처리하기 위해 진리표를 사용하는 것이 더 좋기 때문에 누군가를 돕는 경우를 대비하여 맡길 것입니다.

Answer 4