具有最大异或值的范围内的两个值
Two values from range having maximum xor
我们有两个约束 L 和 R(L<=R)，我们必须找到两个值 i 和 j(l<=i<=j<=R)，使得它们的异或最大。
我已经试过了 O(n^2) 所以想要更好的东西。
如果这是一次性请求，没有预处理：
给定一个范围 [L, R] 你只需要能够找到一个具有 的数字1 在此范围内的数字中的特定位位置。这可以通过位操作轻松完成。
假设你有 L = 0，R = 7，你的二进制数是：
000, 001, 010, ..., 111
当前数是000，要最大化xor你需要找到最多有1的数显着位位置。第一个这样的数字是 4 = 100。现在你正在处理范围 100, 101, ..., 111 和位在第二高的位置。第二高位置的位是 0，因此要最大化 xor，您再次需要一个在该位置上带有 1 的数字。第一个这样的数字是 6 = 110。您可以再次应用完全相同的模式。现在你已经完成了 000 你可以对 001 做同样的事情等等。
一个数的迭代次数是从L到R的最大位数。因此操作总数为O((R-L+1)*log(R-L+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，它们的 XOR 将是您可以获得的最大值。
例如。 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
我们有两个约束 L 和 R(L<=R)，我们必须找到两个值 i 和 j(l<=i<=j<=R)，使得它们的异或最大。
我已经试过了 O(n^2) 所以想要更好的东西。
如果这是一次性请求，没有预处理：
给定一个范围 [L, R] 你只需要能够找到一个具有 的数字1 在此范围内的数字中的特定位位置。这可以通过位操作轻松完成。
假设你有 L = 0，R = 7，你的二进制数是：
000, 001, 010, ..., 111
当前数是000，要最大化xor你需要找到最多有1的数显着位位置。第一个这样的数字是 4 = 100。现在你正在处理范围 100, 101, ..., 111 和位在第二高的位置。第二高位置的位是 0，因此要最大化 xor，您再次需要一个在该位置上带有 1 的数字。第一个这样的数字是 6 = 110。您可以再次应用完全相同的模式。现在你已经完成了 000 你可以对 001 做同样的事情等等。
一个数的迭代次数是从L到R的最大位数。因此操作总数为O((R-L+1)*log(R-L+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，它们的 XOR 将是您可以获得的最大值。
例如。 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