为什么 (a | b) 相当于 a - (a & b) + b？

Question

为什么 (a | b) 相当于 a - (a & b) + b？

oraclebinarycomputer-sciencetheoryproofs

21

我正在寻找在Oracle数据库中执行BITOR()的方法，偶然发现建议使用BITAND()来替代BITOR()，具体操作是将BITOR(a,b)替换为a + b - BITAND(a,b)。

我手动验证了几次，似乎对我能想到的所有二进制数都有效，但我无法快速想出为什么这是正确的数学证明。
能否有人给我讲解一下？

- Brandon Yarbrough

3

我能想到的所有二进制数 - beut :) 很好的问题，船长。 - martin clayton

为什么Oracle有BITAND()但没有BITOR()？ - Thanatos

4个回答

22

假设你有两个二进制数：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

现在我们考虑两个违反条件的数字，也就是说，这两个数字在某个公共位至少有一个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位的两个数字相加时，这些公共位会被"加倍"并产生进位，从而破坏了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 - (a & b)和b相加，我们不会发生进位，而且如果您仔细考虑，我们应该得到与直接执行a | b相同的结果。

a - (a & b) + b = 11100111

- AnT stands with Russia

6

A&B=C，C中任何留下的位都是A和B中都有的位。
要么A-C=D，要么B-C=E，将这些公共位设置为0。由于1-1=0，所以没有进位效应。
D+B或E+A与A+B类似，只是因为我们之前减去了A&B，所以由于清除了D或E中所有公共设置的位，所以不会有进位。
总的结果是A-A&B+B或B-A&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中的两个位都是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

< p > < em >编辑：在没有答案之前，我写了这个问题，然后我的家庭连接出现了2小时的宕机，最终我设法将其发布，之后才注意到已经有两个正确的答案。就我个人而言，我更喜欢参考真值表来计算位运算，因此我会将其保留以帮助某些人。

- dlamblin

4

- Kenny Evitt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ned Batchelder · Accepted Answer

A & B 是 A 和 B 中都为 1 的位。 A - (A & B) 留下了所有仅在 A 中为 1 的位。将 B 加入其中，您将得到在 A 或 B 中为 1 的所有位。

简单地将 A 和 B 相加不起作用，因为当两个位置都为 1 时会产生进位。通过先移除 A 和 B 共同的位，我们知道 (A-(A&B)) 与 B 没有任何公共位，因此将它们加在一起保证不产生进位。