왜 (a | b)가 - (a & b) + b와 동등한 이유는 무엇입니까?

Question

나는 Oracle 데이터베이스를 사용하여 Bitor ()를 수행하는 방법을 찾고 있었고 Bitor (A, B)를 A + B -Bitand (A, B)로 대체하는 대신 Bitand ()를 사용하라는 제안을 발견했습니다.

나는 그것을 몇 번 손으로 테스트하고 내가 생각할 수있는 모든 바이너리 숫자에 대해 작동하는 것처럼 보이지만 이것이 왜 올바른지에 대한 빠른 수학적 증거를 생각할 수는 없습니다.
누군가 나를 깨달을 수 있습니까?

Answer 1

A & B는 A와 B 모두에있는 비트 세트입니다. A- (A & B)는 A에서만 켜져있는 모든 비트를 남깁니다. B에 B를 추가하면 모든 비트를 얻을 수 있습니다. A에서 또는 B에있는 사람들

A와 B의 간단한 추가는 둘 다 1 비트가있는 곳에 운반하기 때문에 작동하지 않습니다. 먼저 A와 B에 공통적 인 비트를 제거함으로써 (A- (A & B))는 B와 공통점이 없으므로 함께 추가하는 것은 캐리를 생성하지 않도록 보장됩니다.

Answer 2

두 가지 바이너리 숫자가 있다고 상상해보십시오. a 그리고 b. 그리고이 숫자가 동시에 같은 비트로 1을 갖지 않는다고 가정 해 봅시다. a 약간의 비트가 있습니다 b 항상 해당 비트에 0이 있습니다. 그리고 다른 방향으로 b 그때는 약간 1이 있습니다 a 그 비트에는 항상 0이 있습니다. 예를 들어

a = 00100011
b = 11000100

이것은 예입니다 a 그리고 b 위 조건을 만족합니다. 이 경우 쉽게 볼 수 있습니다 a | b 정확히 동일합니다 a + b.

a | b = 11100111
a + b = 11100111

이제 우리의 상태를 위반하는 두 개의 숫자를 가져 가자, 즉 두 숫자는 공통 비트에서 적어도 하나의 1을 가지고 있습니다.

a = 00100111
b = 11000100

~이다 a | b 동일합니다 a + b 이 경우? 아니

a | b = 11100111
a + b = 11101011

왜 다른가요? 우리가 때는 다릅니다 + 두 숫자로 1이있는 비트, 우리는 소위 호출을 생성합니다. 나르다: 결과 비트는 0이고 1은 왼쪽의 다음 비트로 운반됩니다. 1 + 1 = 10. 작업 | 캐리가 없습니다 1 | 1 다시 1입니다.

이것은 사이의 차이를 의미합니다 a | b 그리고 a + b 숫자가 공통 비트에 하나 이상의 1이있는 경우에만 발생합니다. 우리가 두 개의 숫자로 1 숫자로 1 숫자를 합치면,이 일반적인 비트는 "두 번"추가되고 캐리를 생성하여 사이의 유사성을 망칩니다. a | b 그리고 a + b.

이제보세요 a & b. 무엇을 하는가 a & b 계산하다? a & b 둘 다있는 모든 비트에서 1을 가진 숫자를 생성합니다. a 그리고 b 우리의 최신 예에서

a =     00100111
b =     11000100
a & b = 00000100

위에서 보았 듯이, 이것들은 정확히 a + b 다릅니다 a | b. 1 인치 a & b 캐리가 발생하는 모든 위치를 나타냅니다.

이제 우리가 할 때 a - (a & b) 우리는 효과적으로 제거하다 (빼) 모든 "불쾌한"비트 a 그리고 그런 비트 만

a - (a & b) = 00100011

번호 a - (a & b) 그리고 b 공통 1 비트가 없으므로 추가하면 a - (a & b) 그리고 b 우리는 캐리에 빠지지 않을 것이며, 당신이 그것에 대해 생각한다면, 우리는 방금했던 것과 같은 결과를 얻어야합니다. a | b

a - (a & b) + b = 11100111

Answer 3

A & B = C는 C에 남은 비트가 A와 B에 설정된 비트입니다.
ac = d 또는 bc = e는 이러한 일반적인 비트를 0으로 설정합니다. 1-1 = 0이므로 운반 효과가 없습니다.
D+B 또는 E+A는 A & B를 빼기 때문에 A+B와 유사합니다. 이전에 A & B를 빼기 때문에 D 또는 E에서 일반적으로 설정된 비트를 모두 제거했기 때문에 캐리가 없을 것입니다.

순 결과는 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의 비트이고 A는 1 ~ 0이기 때문에 A- (A & B) 세트가 A에서 1 ~ 0이기 때문에 다른 경우에 B를 추가하여 다른 경우에 가져 왔기 때문에 + 및 - 작업의 운반 행을 피하십시오. A 또는 B에서 1이지만 0이 모두 0이 아니 었으므로 OR Truth 테이블과 A- (A & B)+B 진실 테이블이 동일합니다.

안구의 또 다른 방법은 A+B가 하단 행의 캐리를 제외하고 거의 A | B와 비슷하다는 것을 알 수 있습니다. A & B는 우리를 위해 그 하단 행을 분리하고, AA & B는 + 테이블에서 두 개의 행을 고립 된 캐스팅을 움직이며 (AA & 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