找到一个数字与序列元素进行异或以获得给定的总和

Question

我最近遇到了以下问题：我们给定了一个整数序列 x_i (x_i < 2^60) n (n < 10^5) 个整数和一个整数 S (S < 2^60) 找到最小的整数 a使得以下内容成立：

.

例如：

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

a的可能解是 21、23、37、39，但最小的是 21。

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

Answer 1

一个人可以从底部一点一点地建立结果。从最低位开始，尝试将 0 和 1 作为 a 的最低位，并查看和异或的最低位是否与 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)

在无解的情况下，代码returns一个大的(>=1e100)浮点数。

这里有一个测试，它在您给定的范围内选择随机值，随机选择一个 a 并计算 S，然后求解。请注意，有时代码会找到比用于计算 S 的代码更小的 a，因为 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

找到一个数字与序列元素进行异或以获得给定的总和

Finding a number to xor with sequence elements to obtain given sum

algorithm

sum

xor