XOR 최소화

2429. XOR 최소화

난이도:중

주제: 욕심, 비트 조작

이 문제는 두 가지 조건을 충족하는 양의 정수 x를 찾는 문제입니다. 주어진 정수 num2와 동일한 수의 설정 비트(이진수 표현에서는 1)를 갖습니다. 그리고 다른 주어진 정수 num1와의 비트별 XOR은 최소화됩니다.

예 1:

• 입력: num1 = 3, num2 = 5
• 출력: 3
• 설명: 3(0011)과 5(0101)에는 모두 두 개의 세트 비트가 있습니다. 3 XOR 3 = 0, 이는 가능한 최소 XOR 값입니다.

예 2:

• 입력: num1 = 1, num2 = 12
• 출력: 3
• 설명: 12(1100)에는 두 개의 세트 비트가 있습니다. 3(0011)에도 2개의 비트가 설정되어 있으며 3 XOR 1 = 2입니다.

제약조건:

• 1 ≤ num1, num2 ≤ 10⁹

솔루션 접근 방식:

핵심은 탐욕스러운 전략이다. XOR 결과를 최소화하기 위해 x의 설정 비트를 num1의 설정 비트와 최대한 정렬하려고 합니다.

1. 설정 비트 계산: num2에서 설정 비트 수를 결정합니다. 이것을 targetBits이라고 부르겠습니다.

2. x 구성: x를 0으로 초기화합니다. 최상위 비트부터 시작하여 num1의 비트를 반복합니다. num1의 각 설정된 비트에 대해 아직 targetBits에 도달하지 않은 경우 해당 비트를 x에 추가하세요. targetBits 요구 사항을 이미 충족했다면 해당 부분을 건너뛰세요. targetBits의 모든 비트를 처리한 후 num1에 도달하지 못한 경우, 최하위 비트부터 시작하여 나머지 비트를 x에 추가합니다.

3. Return x: 생성된 x는 조건을 만족합니다.

PHP 구현:

<code class="language-php"><?php
function minimizeXor(int $num1, int $num2): int {
    $targetBits = countSetBits($num2);
    $x = 0;
    $bitsSet = 0;

    for ($i = 30; $i >= 0; $i--) {
        if (($num1 >> $i) & 1) { // Check if the i-th bit of num1 is set
            if ($bitsSet < $targetBits) {
                $x |= (1 << $i); // Set the i-th bit of x
                $bitsSet++;
            }
        }
    }

    // If we haven't reached targetBits, add remaining bits from LSB
    for ($i = 0; $i < 31 && $bitsSet < $targetBits; $i++) {
        if (!($x & (1 << $i))) { //check if bit is not set yet
            $x |= (1 << $i);
            $bitsSet++;
        }
    }

    return $x;
}

function countSetBits(int $n): int {
    $count = 0;
    while ($n > 0) {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}

// Test cases
echo minimizeXor(3, 5) . PHP_EOL; // Output: 3
echo minimizeXor(1, 12) . PHP_EOL; // Output: 3
echo minimizeXor(10, 7) . PHP_EOL; //Output: 11
?></code>

시간과 공간의 복잡성:

• 시간 복잡도: O(log N), 여기서 N은 num1 및 num2의 최대값입니다. 이는 숫자의 비트를 반복하기 때문입니다.
• 공간 복잡도: O(1), 일정한 추가 공간이 사용됩니다.

이 향상된 솔루션은 문제를 해결하는 더 명확하고 효율적이며 강력한 방법을 제공합니다. 댓글은 각 단계의 논리를 설명합니다.

위 내용은 XOR 최소화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!