有多少组4个数字，使得它们的xor等于0？

我有两个非负整数x和y，它们都有至多30位（所以它们的值在10^9左右）。有多少组4个数字，使得它们的xor等于0？

我想计算4个数字{a_1，a_2，a_3，a_4}有多少组，这样a_1 + a_2 = x和a_3 + a_4 = y，所有这4个数字的xor等于0.

解决此问题的最快算法是什么？

我能想到的最快的方法是将xor方程重新排列为a_1 xor a_2 = a_3 xor a_4。

然后我可以计算出O（x）中左侧的所有值和O（y）中右侧的值，所以整个算法运行在O（x + y）中。

来源

2017-04-04 user128409235

此链接可以帮助您的需求： - https://www.codechef.com/JULY12/problems/GRAYSC – Vinod

其实它与我的问题没有太大的共同之处。 – user128409235

是的，但你可以统计所有与数字有关的数字。 – Vinod

让N(x, y)成为此问题的解决方案的数量。显然N(0, 0)是1，因为唯一的解决方案是（0,0,0,0）。如果x或y是负数，那么就没有办法解决，因为我们要求a1，a2，a3，a4都是非负数。

否则，我们可以继续求解最低位，并生成递归关系。我们写n:0和n:1表示2n + 0和2n + 1（所以0和1是最低位）。

然后：

N(0, 0) = 1 
N(-x, y) = N(x, -y) = 0 
N(x:0, y:0) = N(x, y) + N(x-1, y) + N(x, y-1) + N(x-1, y-1) 
N(x:0, y:1) = N(x:1, y:0) = 0 
N(x:1, y:1) = 4 * N(x, y)

看到这些，人们必须考虑可能的低位对于任何A1，A2，A3，A4。

首先是N(x:0, y:0)。我们需要a1 + a2的低位为0，这意味着a1和a2都是偶数，或者它们都是奇数。如果它们都是奇数，则有一个进位，高位加1的总和必须与x的高位相加。相同的逻辑适用于a3，a4。有4种可能性：a1，a2，a3，a4的所有底部比特都是0，a1的底部比特，a2是1，a3的底部比特，a4是1，a1，a2，a3，a4的底部比特是1。 4例。

其次N(x:0, y:1)和N(x:1, y:0)。如果一个和数是偶数，另一个是奇数，那么就没有办法了：可以检查每个组合的a1，a2，a3，a4的最低位以找出结果。

第三N(x:1, y:1)。 a1和a2中的一个必须是奇数，同样，a3和a4中的一个必须是奇数。有4种可能性，并且在任何情况下都不能携带。

下面是一个完整的解决方案：

def N(x, y): 
    if x == y == 0: return 1 
    if x < 0 or y < 0: return 0 
    if x % 2 == y % 2 == 0: 
     return N(x//2, y//2) + N(x//2-1, y//2) + N(x//2, y//2-1) + N(x//2-1, y//2-1) 
    elif x % 2 == y % 2 == 1: 
     return 4 * N(x//2, y//2) 
    else: 
     return 0

该算法几个递归调用，所以在理论上指数。但在实践中，许多分支快速终止，所以代码运行速度足够快，可以达到2^30的值。但是，当然，您可以添加缓存或使用动态编程表来保证O（log（x）+ log（y））的运行时间。

最后，增加正确性的信心，这里的对抗天真Ø一些测试（XY）解决方案：

def N_slow(x, y): 
    s = 0 
    for a1 in xrange(x + 1): 
     for a3 in xrange(y + 1): 
      a2 = x - a1 
      a4 = y - a3 
      if a1^a2^a3^a4: 
       continue 
      s += 1 
    return s 

for x in xrange(50): 
    for y in xrange(50): 
     n = N(x, y) 
     ns = N_slow(x, y) 
     if n != ns: 
      print 'N(%d, %d) = %d, want %d' % (x, y, n, ns)

来源

2017-04-04 13:15:42

有多少组4个数字，使得它们的xor等于0？

回答

相关问题