XOR 최대화

의문

2개의 정수 l과 r이 주어지면 axorb의 최대값을 찾습니다. 여기서 a와 b는 다음 조건을 충족합니다.l ≤ a ≤ b ≤ r예를 들어 l = 11 및 r = 12 이면

11⊕11 = 0
11⊕12 = 7
12⊕12 = 0

최대값은 7입니다.

순진한 솔루션

순진한 솔루션은 범위의 모든 값에 대해 XOR 값을 계산하고 최대값을 찾는 것입니다.

def maximizingXOR(l, r):
    # Since xor of equal values is 0
    if l == r:
        return 0
    # Set an initial max value
    _max = -1
    # Iterate over all values in the range
    for i in range(l, r+1):
        for j in range(l, r+1):
            # Replace the max value if the xor is greater than the current max value
            _max = max(i ^ j, _max)
    # Return the max value
    return _max

시간 복잡도

O(N2) 여기서 N은 범위, 즉 N = r - l + 1입니다.

효율적인 솔루션

먼저 XOR 연산을 살펴보겠습니다. 이진 값의 경우 XOR은 다음과 같습니다.

0⊕0 = 0
1⊕1 = 0
0⊕1 = 1
1⊕0 = 0

따라서 XOR은 동일한 비트에 대해 0이고 다른 비트에 대해 1입니다.

이제 l에서 r까지의 이진 값 패턴을 고려하십시오. l이 r보다 작기 때문에 l에서 r까지의 첫 번째 비트는 0에서 1로 변경되거나 1로 유지됩니다.

예 1:
l = 10 = (01010)2
r = 20 = (10100)2
여기서 첫 번째 비트는 0에서 1로 변경됩니다.

예 2:
내가 = 10 = (1010)2
r = 15 = (1111)2
여기서 첫 번째 비트는 1로 유지됩니다.

따라서 [l, r] 범위에 있는 두 숫자의 XOR을 취하면 최대 값을 위해 첫 번째 비트가 고정되어 l과 r 자체의 XOR의 첫 번째 비트와 동일합니다.

이제 l과 r의 XOR을 살펴보겠습니다. 최상위 비트에서 범위의 최대 XOR 값이 동일한 최상위 비트를 갖는다는 것을 알고 있습니다. 가장 중요한 비트는 또한 우리가 달성할 수 있는 최대값을 알려줍니다. xxx의 모든 x가 1이 되는 방식입니다.

예 1:
l = 10 = (01010)2
r = 20 = (10100)2
엘 ^ r = (01010) ^ (10100) = (11110)
이제 l ^ r은 (1xxxx) 형식이므로 a와 b를 15와 16(01111과 10000)으로 선택하여 최대 XOR을 (11111)로 얻습니다.

예 2:
내가 = 10 = (1010)2
r = 15 = (1111)2
엘 ^ r = (1010) ^ (1111) = (0101)
이제 l ^ r은 (1xx) 형식이므로 a와 b를 10과 13(1010과 1101)으로 선택하여 최대 XOR을 (111)로 얻습니다.

따라서 최대 XOR 값을 얻으려면 (l ^ r)만 있으면 됩니다. 먼저 (l ^ r)를 계산한 다음 이 값의 최상위 비트부터 모두 1을 더하여 최종 결과를 얻습니다.

효율적인 솔루션 1

def maximizingXOR(l, r):
    result = 1
    xor = l ^ r  # 1xxx
    # iterate for (MSB+1) times
    while xor:
        result <<= 1
        xor >>= 1
    # return MSB with all added 1s i.e. if xor was 1xxx return 1111
    return result - 1

시간 복잡도

O(logN) 여기서 N은 범위, 즉 N = r - l + 1입니다.

효율적인 솔루션 2

또 다른 해결책은 로그 함수를 직접 사용하여 최상위 비트를 얻는 것입니다.

import math

def maximizingXOR(l, r):
    # log(0) is not possible, so condition to prevent it
    if l == r:
        return 0
    return (1 << (int(math.log(l ^ r, 2)) + 1)) - 1

시간 복잡도

O(1) 로그 함수를 가정하면 O(1) 시간이 걸립니다.