algorithm - 具有最大异或值的范围内的两个值

Question

我们有两个约束 L 和 R(L<=R)，我们必须找到两个值 i 和 j(l<=i<=j<=R)，使得它们的异或最大。

我已经试过 O(n^2) 所以想要更好的东西。

Answer 1

这是您可以使用的解决方案(这会在 log(R) 中给出答案)

让我用一个例子来解释:

令 L=34，R=45。将它们表示为位数组:

L = 100010     R = 101101

你从左边开始，直到找到第一个不匹配的形式:

L[i] = 0 and R[i] = 1

你总是会找到这个，因为 L < R。(如果 L==R，这是微不足道的情况，答案是 0)

从这里开始，将L的每一位更改为1，将R的每一位更改为0。

您得到的数字将是您的i 和j，它们的异或将是您可以获得的最大值。

例如。 34 和 45

  100010 and 101101
1st mismatch at index 2 [0-based] 
From there, change all L[i] to 1 and all R[i] to 0
=> i = 100111 and j = 101000
=> i = 39 and j = 40
and i^j = 15