如何找到 xor ==n 的一对数字
How to find pair of numbers whose xor ==n
我是位操作的新手，我有这个问题，我不知道如何解决它
问题
查找 xor 等于 n 和 return 最小差异对
的对
example n=5 possible pairs are 1-4,9-12 and so on
result is 4-1 as the diffrence of 4-1 is minimum
这里不适用暴力破解，因为范围非常大，可达 1
假设 n 为正。首先使用 O(log n) 循环将 n 减少到 m，这是小于 n 的 2 的最高幂：
m = n
while m & (m-1):
m = m & (m-1)
那么你的答案将是m和n-m。
让我试着给出一个证明的草图：
很容易理解为什么这适用于 m ^ (n-m) == n。现在我证明为什么这对有最小的差异。令 m ^ x == n 对于某些 m 和 x 并且不失一般性，假设 m > x。我们不假设 m == x 因为否则 n==0。在保持 m ^ x == n 的同时，如果我们将两个相同的零位翻转为 1，我们将它们增加相同的数量，因此它们的差值 m-x 仍然相同。因此我们也可以假设 m 和 x 上的位永远不会在同一位置上都为 1。如果我们翻转在 m 上为 0 但在 x 上为 1 的位，它将在 x 上减少但在 m 上增加并且差异 m-x 将是更大。如果我们翻转在 m 上为 1 但在 x 上为 0 的位，差异 可能 更小。因此，具有最小差异的对使得我们无法进行最后一次翻转，即 m 翻转 m 上的任何 1 位将使 m < x.
我是位操作的新手，我有这个问题，我不知道如何解决它
问题
查找 xor 等于 n 和 return 最小差异对
example n=5 possible pairs are 1-4,9-12 and so on
result is 4-1 as the diffrence of 4-1 is minimum
这里不适用暴力破解，因为范围非常大，可达 1
假设 n 为正。首先使用 O(log n) 循环将 n 减少到 m，这是小于 n 的 2 的最高幂：
m = n
while m & (m-1):
m = m & (m-1)
那么你的答案将是m和n-m。
让我试着给出一个证明的草图：
很容易理解为什么这适用于 m ^ (n-m) == n。现在我证明为什么这对有最小的差异。令 m ^ x == n 对于某些 m 和 x 并且不失一般性，假设 m > x。我们不假设 m == x 因为否则 n==0。在保持 m ^ x == n 的同时，如果我们将两个相同的零位翻转为 1，我们将它们增加相同的数量，因此它们的差值 m-x 仍然相同。因此我们也可以假设 m 和 x 上的位永远不会在同一位置上都为 1。如果我们翻转在 m 上为 0 但在 x 上为 1 的位，它将在 x 上减少但在 m 上增加并且差异 m-x 将是更大。如果我们翻转在 m 上为 1 但在 x 上为 0 的位，差异 可能 更小。因此，具有最小差异的对使得我们无法进行最后一次翻转，即 m 翻转 m 上的任何 1 位将使 m < x.