求b使a + b的总和等于xor b

Question

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

我试过了，但是对于巨大的价值，解决方案用尽了内存

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

期望通过大价值

Answer 1

您需要查看XOR的属性。开始与XOR真值表，如应用于单个位：

 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，对应的位都有2个可能的罗格值1，无论使用还是B，都将导致完全相同的结果。因此，对于任何价值有至少1值哪里。如果A中的位设置为零（并且B可以超过2 ** 50，则此类位的数量是无限的），那么B会有更多选择。A ^ BA + BABA + B == A ^ B

如果您只需要生成一个数字，那么最简单的事情就是让您专注于这些表中的A = 0, B = 1和A = 1, B = 0选项。因为如果你拿了的价值A，并与异或它只有 1秒，你会变成的所有位A到他们的绝对对立，所以创建比特组B = 1为每个A = 0和B = 0每一个A = 1。

例如，采用数字42，它以二进制表示为101010（1 x 32、0 x 16、1 x 8、0 x 4、1 x 2和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()方法：

>>> (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。我不会为此生成代码，因为for A = 2，它包括4到2 ** 50之间的所有整数，因此B除了，还有1.125.899.906.842.621的不同可能值B = 1。