给定两个数的XOR和SUM,如何找到满足它们的对的数量？

Question

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

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

例如,如果XOR是5其和9有4满足SUM和XOR对.它们是(2,?7),(3,?6),(6,?3),(7,?2).所以2+7=9和2^7=5.

我只想找到满足SUM和XOR的对的数量.所以在我提到的例子中,答案4就足够了.我不需要知道哪些对满足它们.

我从这里解决了这个问题.

我在这里查了一个答案.它提供的O(n)解决方案还不够.

有一个编辑提供了解决这个问题的方法.它可以在这里找到.(寻找627A的解决方案)

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

我怎么到达那个？其余的步骤对我来说不清楚.

如果有人能提出如何解决这个问题或解释他们的解决方案,请帮助.

Answer 1

想想a+b = (a XOR b) + (a AND b)*2当你做二进制加法时会发生什么.从您的示例,a = 010和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是左移.)

通过这个等式我们可以计算a AND b.

现在算你想要的数字,我们看的每个位a XOR b和a AND b一个接一个和繁殖所有的可能性.(让我写a[i]为i的个位a)

• 如果a[i] XOR b[i] = 0和a[i] AND b[i] = 0,那么a[i] = b[i] = 0.这个位只有一种可能性.

• 如果a[i] XOR b[i] = 0和a[i] AND b[i] = 1,那么a[i] = b[i] = 1.这个位只有一种可能性.

• 如果a[i] XOR b[i] = 1和a[i] AND b[i] = 0,那么a[i] = 1和b[i] = 0反之亦然.两种可能性.

• 这是不可能的a[i] XOR b[i] = 1和a[i] AND b[i] = 1.

从你的例子,a XOR b = 101和a AND b = 010.我们有答案2*1*2 = 4.

Answer 2

a AND b是两个数字中的位。所以这些总和是两倍。a XOR b是仅出现在其中一个数字中的位，因此它们在总和中只应计入一次。

下面是一个例子：

• a = 4 = 1*2^2 + 0*2^1 + 0*2^0 (or just 100)
• b = 13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 (or just 1101)
• a + b = (1*2^2 + 0*2^1 + 0*2^0) + (1*2^3 + 1*2^2 + 0*2^1 + 1*2^0) = 1*2^3 + 2*2^2 + 0*2^1 + 1*2^0

请注意在最后一行中，两个数字 ( 2^2) 中的位如何在总和中计算两次，而其余部分仅计算一次！

要解决您的问题，您需要找到加起来为总和的所有对 (a, b)。你想要做的是：

1. 从 SUM 中减去 XOR 值。你只剩下2*(a AND b).
2. 除以 2。您现在拥有应在 a 和 b 中设置的所有位。
3. 由于您有 XOR 值，您确切地知道应该在a 和 b之一中设置哪些位，而您刚刚计算的 AND 值是应该在它们两个中设置的位。因此，您分别列出了在 a 或 b 中设置位的所有排列。

继续我之前的例子：

• a AND b = 0100 （始终设置在两者中）
• a XOR b = 1001 （我们需要尝试这些的所有排列）

我们得到这些排列作为解决方案：

• a = 0100 + 0000 = 0100, b = 0100 + 1001 = 1101 => (4, 13)
• a = 0100 + 0001 = 0101, b = 0100 + 1000 = 1100 => (5, 12)
• a = 0100 + 1000 = 1100, b = 0100 + 0001 = 0101 => (12, 5)
• a = 0100 + 1001 = 1101, b = 0100 + 0000 = 0100 => (13, 4)