对于所有整数对a，b（l≤a≤b≤r）的xor b的最大值

-1

该问题要求找到所有整数对的xor b的最大值整数对a，b（ l≤a≤b≤r）。如果l和R是8和16，答案是31，实际上是15或16.我看到这段代码，它给出正确的输出，但逻辑部分不清楚。对于所有整数对a，b（l≤a≤b≤r）的xor b的最大值

int main() { 
    cin >> A >> B; 
    ll num = 1; 
    while (A/num != B/num) { 
     num *= 2; 
    } 
    cout << num - 1 << "\n"; 
    return 0; 
}

来源

2016-02-24 satyajeet jha

好了，我可以很容易崩溃的代码。通过输入相同的数字两次。如果l = r，则算法崩溃，但是由于l = a = b = r，所以xor b的最大值显然为0。（1 /（2^n））=（r /（2^n））。有这样一个n，因为我们可以选择制造2^n> r。并且n> 0因为l < r。选择最小的这样的n。

在这种情况下，对于所有a，a /（2^n）具有相同的值，l≤a≤r。这意味着以位n开始的^ b中的所有位都是零。因此，可以用l模（2^n），r模（2^n）代替l，r。

另一方面，n被选择为尽可能小。因此，位n-1设置在r中，而位n-1在l中被清除。因此2 ^（n-1），r≥2^（n-1）。我们可以选择a = 2 ^（n-1） - 1，b = 2 ^（n-1）。那么l≤a≤b≤r，并且xor b = 2^n - 1。由于我们证明xor b总是小于2^n，但可以是2^n - 1，因此2^n - 1是最大的值。

算法的算法究竟是什么，除非l = r没有正确处理。

来源

2016-02-24 20:27:43 gnasher729

ü可以用一个例子更清楚地解释它，以两个数字说，8和16 –

让我们用L = 8，且r = 16的实例中，或

l = 00010 
r = 00001

的代码做什么，直到号码是相同的，则移位位：

num=2 num=4 num=8 num=16 num=32 

00100 01000 10000 00000 00000 
00010 00100 01000 10000 00000 -> done : max xor is 32-1

这个作品，因为您可以得到的最大xor数是尽可能多的位设置为1的数字，并且一般来说，如果您有

l = 0001010101010101011111111111110000001010101010... 
r = 0010101010101010101101010101010100001010101010... 
            ^...starting from here they are 
             the same (no matter what)

，你可以从一个XOR B获得的L <一个< b < R上的最大结果是

111111111111111111111111111111110000000000000000000...

来源

2016-02-24 20:43:43 user463035818

对于所有整数对a，b（l≤a≤b≤r）的xor b的最大值

回答

相关问题