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

Question

我正在寻找一种方法来使用Oracle数据库进行BITOR()并且遇到了一个建议,只需使用BITAND()代替BITOR(a,b)替换为+ 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.

这意味着之间的差a | b和a + b发生当且仅当数字共同具有位的至少一个1.当我们将两个数字与公共位中的1相加时,这些公共位被"加"两次并产生一个进位,这破坏了a | b和之间的相似性a + b.

现在看看a & b.是什么a & b计算？a & b产生具有在所有位1的数量都在那里a,并b有1.在我们的最新的例子

a =     00100111
b =     11000100
a & b = 00000100

如上所述,这些正是与之a + b不同的部分a | b.1 in 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,所以由于清除了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中的位,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

编辑:所以我在得到答案之前写了这个,然后在我的家庭连接上有两个小时的停机时间,我终于设法发布它,之后才注意到它已经被正确回答了两次.就个人而言,我更喜欢使用真值表来计算按位运算,所以我会留下它以防万一它可以帮助某人.