有多少組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？

回答

相關問題