给定两个数字的XOR和SUM，如何找到满足它们的对的数量? [英] Given an XOR and SUM of two numbers, how to find the number of pairs that satisfy them?

问题描述

我认为这个问题可能有点令人困惑.所以，我会先解释一下.

I think the question may be a bit confusing. So, I'll try to explain it first.

假设给出两个数字的XOR和SUM. (请注意，可能有多个对可以满足此要求.)

Let's say the XOR and SUM of two numbers are given. (Note that there are multiple pairs that may satisfy this.)

例如，如果XOR为5并且SUM为9，则存在满足SUM和XOR的4对.它们是(2, 7)，(3, 6)，(6, 3)，(7, 2).所以2+7=9和2^7=5.

For example, If the XOR is 5 and the SUM is 9 there are 4 pairs satisfying the SUM and XOR. They are (2, 7), (3, 6), (6, 3), (7, 2). So 2+7=9 and 2^7=5.

我只想找到满足SUM和XOR的对的 number .因此，在示例中，我提到答案4就足够了.我不需要知道哪对满足他们.

I just want to find the number of pairs that satisfies the SUM and XOR. So in the example I mentioned the answer 4 is enough. I don't need to know which pairs satisfy them.

我从此处解决了这个问题.

I took this problem from here.

我在此处.它提供的O(n)解决方案还不够.

I checked for an answer here. It provides an O(n) solution which is not enough.

有一篇社论提供了有关此问题的解决方案.可以在此处找到. (寻找627A的解决方案)

There is an Editorial that provides the solution on this problem. It can be found here. (Look for the solution of 627A)

问题是我不明白解决方案.根据我的总结，他们使用了这样的公式，
(如果有两个数字a和b)， a+b = (a XOR b) + (a AND b)*2

The problem is that I can't understand the solution. From what I could sum up they used a formula like this,
(If there are two numbers a and b) then, a+b = (a XOR b) + (a AND b)*2

我该如何到达?其余步骤对我来说还不清楚.

How do I arrive to that? The rest of the steps are unclear to me.

如果任何人都可以提供解决方案或解释其解决方案的想法，请提供帮助.

If anyone could provide an idea on how to solve this or explain their solution, please help.

推荐答案

将a+b = (a XOR b) + (a AND b)*2视为您进行二进制加法运算时会发生的情况.在您的示例中，a = 010和b = 111:

Think of a+b = (a XOR b) + (a AND b)*2 as exactly what happen when you do binary addition. From your example, a = 010 and b = 111:

 010
 111
 ---
1001 = 101 + 100

对于每个位，请添加a和b(0+0=0，0+1=1，1+0=1，1+1=0)中的位，它们恰好是a XOR b 加前一个加法的进位位，即如果a和b的前两个位都为1，那么我们也将其相加.这恰好是(a AND b)*2(请记住，乘以2是左移).

For each bit, you add bits from a and b (0+0=0, 0+1=1, 1+0=1, 1+1=0, which is exactly a XOR b plus the carry-in bit from the previous addition, i.e. if both previous bits for a and b are 1, then we add it also. This is exactly (a AND b)*2. (Remember that multiplication by 2 is a shift left.)

有了这个等式，我们可以计算出a AND b.

With that equation we can calculate a AND b.

现在要计算所需的数字，我们逐一查看a XOR b和a AND b的每个位，并将所有可能性相乘. (让我为a的第i位写a[i])

Now to count the number you want, we look at each bits of a XOR b and a AND b one-by-one and multiply all possibilities. (Let me write a[i] for the i-th bit of a)

• 如果a[i] XOR b[i] = 0和a[i] AND b[i] = 0，则a[i] = b[i] = 0.这种可能性只有一种.

• If a[i] XOR b[i] = 0 and a[i] AND b[i] = 0, then a[i] = b[i] = 0. Only one possibility for this bit.

如果a[i] XOR b[i] = 0和a[i] AND b[i] = 1，则a[i] = b[i] = 1.这种可能性只有一种.

If a[i] XOR b[i] = 0 and a[i] AND b[i] = 1, then a[i] = b[i] = 1. Only one possibility for this bit.

如果a[i] XOR b[i] = 1和a[i] AND b[i] = 0，则a[i] = 1和b[i] = 0，反之亦然.两种可能性.

If a[i] XOR b[i] = 1 and a[i] AND b[i] = 0, then a[i] = 1 and b[i] = 0 or vice versa. Two possibilities.

不可能有a[i] XOR b[i] = 1和a[i] AND b[i] = 1.

在您的示例中，a XOR b = 101和a AND b = 010.我们有答案2*1*2 = 4.

From your example, a XOR b = 101 and a AND b = 010. We have the answer 2*1*2 = 4.

这篇关于给定两个数字的XOR和SUM，如何找到满足它们的对的数量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！