XORを最小限に抑える

2429。 XOR を最小化

難易度: 中

トピック: 貪欲なビット操作

この問題では、2 つの条件を満たす正の整数 x を見つけることが求められます。その整数は、指定された整数 num2 と同じ数のセット ビット (バイナリ表現では 1) を持ちます。そして、別の指定された整数 num1 とのビットごとの XOR が最小化されます。

例 1:

• 入力: num1 = 3、num2 = 5
• 出力: 3
• 説明: 3 (0011) と 5 (0101) には両方とも 2 つのセットビットがあります。 3 XOR 3 = 0、これは可能な最小の XOR 値です。

例 2:

• 入力: num1 = 1、num2 = 12
• 出力: 3
• 説明: 12 (1100) には 2 つのセットビットがあります。 3 (0011) にも 2 つのセットビットがあり、3 XOR 1 = 2 になります。

制約:

• 1 ≤ num1、num2 ≤ 10⁹

解決策のアプローチ:

鍵となるのは貪欲な戦略です。 XOR の結果を最小限に抑えるために、x の設定ビットを num1 の設定ビットとできる限り揃えたいと考えます。

1. Count Set Bits: num2 に設定されているビットの数を決定します。これを targetBits と呼びましょう。

2. Construct x: x を 0 に初期化します。最上位ビットから始めて、num1 のビットを反復処理します。 num1 に設定された各ビットについて、まだ targetBits に到達していない場合は、そのビットを x に追加します。 targetBits 要件をすでに満たしている場合は、その部分をスキップしてください。 targetBits のすべてのビットを処理しても num1 に到達していない場合は、残りのビットを最下位ビットから始めて x に追加します。

3. Return 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)、一定の追加スペースが使用されます。

この改良されたソリューションは、問題を解決するためのより明確、より効率的、より堅牢な方法を提供します。 コメントは各ステップのロジックを説明しています。

以上がXORを最小限に抑えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。