当前位置：文江博客话题详情

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

发布于 2024-08-08 10:59:17 字数 179 浏览 6 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

时光是把杀猪刀 2024-08-15 10:59:17

A& B 是 A 和 B 中都打开的位的集合。A - (A & B) 留给您仅在 A 中打开的所有位。将 B 添加到其中，您将获得所有打开的位A 中的值或 B 中的值。A

和 B 的简单加法不起作用，因为两者都有 1 位。通过首先删除 A 和 B 共有的位，我们知道 (A-(A&B)) 将没有与 B 共有的位，因此将它们加在一起可以保证不会产生进位。

回复收藏 0 原文

此生挚爱伱 2024-08-15 10:59:17

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

Is 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。 a & 中的 1 b 表示所有将发生进位的位置。

现在，当我们执行 a - (a & b) 时，我们有效地删除（减去）a 中的所有“违规”位，并且只有这样的位位

a - (a & b) = 00100011

数字 a - (a & b) 和 b 没有公共的 1 位，这意味着如果我们添加 a - (a & b)< /code> 和 b 我们不会遇到进位，而且，如果你仔细想想，我们最终应该得到与刚刚执行 a | 相同的结果。 b

a - (a & b) + b = 11100111

Imagine you have two binary numbers: a and b. And let's say that these number never have 1 in the same bit at the same time, i.e. if a has 1 in some bit, the b always has 0 in the corresponding bit. And in other direction, if b has 1 in some bit, then a always has 0 in that bit. For example

a = 00100011
b = 11000100

This would be an example of a and b satisfying the above condition. In this case it is easy to see that a | b would be exactly the same as a + b.

a | b = 11100111
a + b = 11100111

Let's now take two numbers that violate our condition, i.e. two numbers have at least one 1 in some common bit

a = 00100111
b = 11000100

Is a | b the same as a + b in this case? No

a | b = 11100111
a + b = 11101011

Why are they different? They are different because when we + the bit that has 1 in both numbers, we produce so called carry: the resultant bit is 0, and 1 is carried to the next bit to the left: 1 + 1 = 10. Operation | has no carry, so 1 | 1 is again just 1.

This means that the difference between a | b and a + b occurs when and only when the numbers have at least one 1 in common bit. When we sum two numbers with 1 in common bits, these common bits get added "twice" and produce a carry, which ruins the similarity between a | b and a + b.

Now look at a & b. What does a & b calculate? a & b produces the number that has 1 in all bits where both a and b have 1. In our latest example

a =     00100111
b =     11000100
a & b = 00000100

As you saw above, these are exactly the bits that make a + b differ from a | b. The 1 in a & b indicate all positions where carry will occur.

Now, when we do a - (a & b) we effectively remove (subtract) all "offending" bits from a and only such bits

a - (a & b) = 00100011

Numbers a - (a & b) and b have no common 1 bits, which means that if we add a - (a & b) and b we won't run into a carry, and, if you think about it, we should end up with the same result as if we just did a | b

a - (a & b) + b = 11100111

回复收藏 0 原文

凯凯我们等你回来 2024-08-15 10:59:17

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

编辑：所以我在有答案之前写了这篇文章，然后就有了我的家庭连接出现了大约 2 个小时的停机时间，我终于成功地发布了它，之后才注意到它已经被正确回答了两次。就我个人而言，我更喜欢参考真值表来计算按位运算，所以我会保留它，以防它对某人有帮助。

A&B = C where any bits left set in C are those set in both A and in B.
Either A-C = D or B-C = E sets just these common bits to 0. There is no carrying effect because 1-1=0.
D+B or E+A is similar to A+B except that because we subtracted A&B previously there will be no carry due to having cleared all commonly set bits in D or E.

The net result is that A-A&B+B or B-A&B+A is equivalent to A|B.

Here's a truth table if it's still confusing:

 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

Notice the carry rows in the + and - operations, we avoid those because A-(A&B) sets cases were both bits in A and B are 1 to 0 in A, then adding them back from B also brings in the other cases were there was a 1 in either A or B but not where both had 0, so the OR truth table and the A-(A&B)+B truth table are identical.

Another way to eyeball it is to see that A+B is almost like A|B except for the carry in the bottom row. A&B isolates that bottom row for us, A-A&B moves those isolated cased up two rows in the + table, and the (A-A&B)+B becomes equivalent to A|B.

While you could commute this to A+B-(A&B), I was afraid of a possible overflow but that was unjustified it seems:

#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

Edit: So I wrote this before there were answers, then there was some 2 hours of down time on my home connection, and I finally managed to post it, noticing only afterwards that it'd been properly answered twice. Personally I prefer referring to a truth table to work out bitwise operations, so I'll leave it in case it helps someone.

回复收藏 0 原文