Người ta có thể xây dựng kết quả lên từng chút một từ đáy. Bắt đầu với bit thấp nhất, hãy thử 0 và 1 là bit thấp nhất của a và xem bit thấp nhất của tổng-xor khớp với bit tương ứng của S. Sau đó thử bit thấp nhất tiếp theo, truyền bất kỳ thao tác nào từ bước trước đó.
Theo thuật toán này, có thể có 0, 1 hoặc 2 lựa chọn cho mỗi bit a, vì vậy trong trường hợp xấu nhất, chúng tôi có thể cần khám phá các nhánh khác nhau và chọn nhánh mang lại kết quả nhỏ nhất. Để tránh hành vi theo cấp số nhân, chúng tôi lưu vào bộ nhớ cache các kết quả đã xem trước đây để mang theo một bit nhất định. Điều đó mang lại độ phức tạp tồi tệ nhất của O (kn) trong đó k là số bit tối đa trong kết quả, và n là giá trị lớn nhất của số thực hiện cho danh sách đầu vào có độ dài n.
Dưới đây là một số mã Python mà thực hiện điều này:
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)
Trong trường hợp không có giải pháp, mã trả về một lớn (> = 1e100) số dấu chấm động.
Và đây là bài kiểm tra chọn giá trị ngẫu nhiên trong phạm vi bạn đã đưa ra, chọn ngẫu nhiên a và tính S rồi giải quyết. Lưu ý rằng đôi khi mã tìm thấy số a nhỏ hơn số được sử dụng để tính S vì giá trị của a không phải lúc nào cũng duy nhất.
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
.