python - 找到 b 使得 a + b 的总和等于 a xor b

Question

我正在编写接受 A 1<A<2*50 的代码找到一个值 b 使得 A+B==A^B

我试过了，但是对于巨大的值(value)解决方案内存不足

def solve(A):
   if A==1:
       return 2
   for i in xrange(1,A+1):
        if A+i==A^i:
            return i

期望通过大值

Answer 1

你需要看看异或的性质。从应用于单个位的异或真值表开始:

 A  |  B  |  A ^ B
----|-----|--------
 0  |  0  |    0
 0  |  1  |    1
 1  |  0  |    1
 1  |  1  |    0

将此与 A + B 进行比较

 A  |  B  |  A + B
----|-----|--------
 0  |  0  |    0
 0  |  1  |    1
 1  |  0  |    1
 1  |  1  |    10    # requires two bits!

因此，对于 A 的任何给定位值，B 中相应位的 2 个可能值中存在 Rutger 1，这将导致恰好 无论使用 A ^ B 还是 A + B 都具有相同的外锥。因此，对于 A 的任何值，B 至少有 1 个值，其中 A + B == A ^ B。如果A中有位设置为0(如果B可以超过2**50，那么这样的位有无限多)，那么B的选项就多了。

如果您只需要生成一个 数字，那么最简单的做法就是让您专注于A = 0, B = 1 和 A = 1, B = 0 这些表中的选项。因为如果你获取 A 的值并用仅 1 对它进行异或运算，你会将 A 的所有位都变成它们的对立面，因此创建为每个 A = 0 设置 B = 1 的位，为每个 A = 1< 创建 B = 0/.

以数字42为例，它用二进制表示为101010 (1 x 32, 0 x 16, 1 x 8, 0 x 4, 1 x 2 and 0 x 1,总和为 42)。将其与二进制数 11111(十进制为 63)进行异或运算，然后翻转所有位:

>>> format(42, '06b')  # 42 in binary, the 6 lower bits
'101010'
>>> 0b111111  # binary number with 6 bits, all 1
63
>>> format(42 ^ 0b111111, '06b')  # XOR with 63, still 6 bits
'010101'
>>> 42 ^ 0b111111  # now in decimal
21

那是你最好的 B 候选人，对这些求和并在这些上使用 XOR 得到一个所有 6 位都设置的数字，所以又是 63:

>>> 42 + 21
63
>>> 42 ^ 21
63

你怎么知道要咬多少？使用 int.bit_length() method :

>>> (42).bit_length()
6

如何生成一个使用任意位数的整数，并将其全部设置为 1？通过对位长度取 2 的幂，然后减去 1:

>>> 2 ** 6
64
>>> 2 ** 6 - 1
63
>>> format(2 ** 6 - 1, 'b')
'111111'

所以解决方案是:

def solve(a):
    return a ^ 2 ** a.bit_length() - 1

这也简单地解决了 2 ** 50 的问题:

>>> A = 42
>>> B = solve(A)
>>> A + B == A ^ B
True
>>> A = 2 ** 50
>>> B = solve(A)
>>> A + B == A ^ B
True

如果您要查看 A 具有 0 位的所有位置，那么您可以为 B 生成 很多 个值。只需从 a ^ 2 ** 50 - 1 开始，然后将现在设置为 1 的每个位(在中设置为 0 A) 并生成所有可能的组合，将它们再次设置为 0。这些组合中的每一个都是 B 的另一个有效值。我不打算为此生成代码，因为对于 A = 2，这包括 4 到 2 ** 50 之间的所有整数，因此 B 有 1.125.899.906.842.621 个不同的可能值，除了 B = 1。