找到了一些与序列的元素异或获得给定和

我最近遇到以下问题：我们给出一个整数序列n (n < 10^5)整数x_i (x_i < 2^60)和整数S (S < 2^60)发现a使得下式成立的最小整数：找到了一些与序列的元素异或获得给定和

。

例如：a

x = [1, 2, 5, 10, 50, 100] 
S = 242

可能的解决方案是21，23，37，39，但最小的是21

(1^21) + (2^21) + (5^21) + (10^21) + (50^21) + (100^21) 
= 20 + 23 + 16 + 31 + 39 + 113 
= 242

来源

2017-04-09 Abdul Haran

人们可以从构建结果向上逐位底端。从最低位开始，尝试0和1作为a的最低位，并查看sum-xor的最低位是否与S的相应位匹配。然后尝试下一个最低位，传播上一步中的任何进位。

按照这个算法，a的每一位可能有0,1或2个选择，所以在最坏的情况下，我们可能需要探索不同的分支并选择一个给出最小结果的分支。为了避免指数行为，我们缓存先前看到的进位结果。这产生了O（kn）的最坏情况复杂度，其中k是结果中的最大比特数，并且n是给定输入列表长度为n的进位的最大值。

下面是实现这一些Python代码：

max_shift = 80 

def xor_sum0(xs, S, shift, carry, cache, sums): 
    if shift >= max_shift: 
     return 1e100 if carry else 0 
    key = shift, carry 
    if key in cache: 
     return cache[key] 
    best = 1e100 
    for i in xrange(2): 
     ss = sums[i][shift] + carry 
     if ss & 1 == (S >> shift) & 1: 
      best = min(best, i + 2 * xor_sum0(xs, S, shift + 1, ss >> 1, cache, sums)) 
    cache[key] = best 
    return cache[key] 

def xor_sum(xs, S): 
    sums = [ 
     [sum(((x >> sh)^i) & 1 for x in xs) for sh in xrange(max_shift)] 
     for i in xrange(2)] 
    return xor_sum0(xs, S, 0, 0, dict(), sums)

在这种情况下也没有解决，代码返回一个大的（> = 1e100）浮点数。

这里是一个测试，在你给出的范围内选取随机值，随机挑选a并计算S，然后求解。请注意，由于a的值不总是唯一的，因此有时代码会找到比用于计算S的代码更小的a。

import random 
xs = [random.randrange(0, 1 << 61) for _ in xrange(random.randrange(10 ** 5))] 
a_original = random.randrange(1 << 61) 
S = sum(x^a_original for x in xs) 
print S 
print xs 

a = xor_sum(xs, S) 
assert a < 1e100 
print 'a:', a 
print 'original a:', a_original 

assert a <= a_original 

print 'S', S 
print 'SUM', sum(x^a for x in xs) 

assert sum(x^a for x in xs) == S

来源

2017-04-09 17:43:28

找到了一些与序列的元素异或获得给定和

回答

相关问题