最小化異或

2429。最小化異或

難度：中

主題：貪婪、位元操作

此問題要求您找到一個正整數x，它滿足兩個條件：它具有與給定整數num2 相同數量的設定位（二進位表示形式為1），其與另一個給定整數num1 的位元異或被最小化。

範例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）也有兩個設定位，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. 回傳x:構造的x將滿足條件。

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
?>

時間與空間複雜度：

• 時間複雜度： O(log N)，其中 N 是 num1 和 num2 的最大值。 這是因為我們迭代數字的位元。
• 空間複雜度： O(1)，使用恆定的額外空間。

這個改良的解決方案提供了更清晰、更有效率、更穩健的方法來解決問題。 註釋解釋了每一步的邏輯。

以上是最小化異或的詳細內容。更多資訊請關注PHP中文網其他相關文章！