oracle - 为什么 (a | b) 等价于 a - (a & b) + b？

Question

我正在寻找一种使用 Oracle 数据库执行 BITOR() 的方法，并遇到了一个建议，即只使用 BITAND()，将 BITOR(a,b) 替换为 a + b - BITAND(a,b)。

我手动测试了几次，并验证它似乎适用于我能想到的所有二进制数，但我想不出快速的数学证明来证明为什么这是正确的。
有人可以启发我吗？

Answer 1

A & 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

现在让我们取两个违反我们条件的数字，即两个数字在某个公共位中至少有一个 1

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 | b。a + b当我们将两个数字与公共位中的 1 相加时，这些公共位会被加“两次”并产生一个进位，这会破坏 和 之间的相似a | b性a + b。

现在看看a & b。计算什么a & b？a & b产生在所有位中都为 1a且两者b都为 1 的数字。在我们最新的示例中

a =     00100111
b =     11000100
a & b = 00000100

正如您在上面看到的，这些正是a + b与a | b. 中的 1a & 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，所以由于清除了 D 或 E 中的所有常用设置位，因此不会有进位。

最终结果是 AA&B+B 或 BA&B+A 等价于 A|B。

如果仍然令人困惑，这是一个真值表：

一个 | 乙| 或一个 | 乙| ＆A | 乙| - 一个 | 乙| +
---+---+--- ---+---+--- ---+---+--- ---+---+---
 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 为我们隔离了最下面的一行，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