對於所有整數對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的最大值

回答

相關問題