왜 (a | b)가 - (a & b) + b와 동등한 이유는 무엇입니까?
-
05-07-2019 - |
문제
나는 Oracle 데이터베이스를 사용하여 Bitor ()를 수행하는 방법을 찾고 있었고 Bitor (A, B)를 A + B -Bitand (A, B)로 대체하는 대신 Bitand ()를 사용하라는 제안을 발견했습니다.
나는 그것을 몇 번 손으로 테스트하고 내가 생각할 수있는 모든 바이너리 숫자에 대해 작동하는 것처럼 보이지만 이것이 왜 올바른지에 대한 빠른 수학적 증거를 생각할 수는 없습니다.
누군가 나를 깨달을 수 있습니까?
해결책
A & B는 A와 B 모두에있는 비트 세트입니다. A- (A & B)는 A에서만 켜져있는 모든 비트를 남깁니다. B에 B를 추가하면 모든 비트를 얻을 수 있습니다. A에서 또는 B에있는 사람들
A와 B의 간단한 추가는 둘 다 1 비트가있는 곳에 운반하기 때문에 작동하지 않습니다. 먼저 A와 B에 공통적 인 비트를 제거함으로써 (A- (A & B))는 B와 공통점이 없으므로 함께 추가하는 것은 캐리를 생성하지 않도록 보장됩니다.
다른 팁
두 가지 바이너리 숫자가 있다고 상상해보십시오. 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
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 시간의 다운 타임이 있었고, 마침내 그것을 게시 할 수 있었고, 나중에 두 번 올바르게 대답했다는 것을 알았다. 개인적으로 나는 진실 테이블을 언급하는 것을 선호하여 약간의 작업을 수행 할 수 있으므로 누군가를 돕는 경우에 따라 떠날 것입니다.