Kurangkan XOR

2429. Minimumkan XOR

Kesukaran: Sederhana

Topik: Tamak, Manipulasi Bit

Masalah ini mencabar anda untuk mencari integer positif, x, yang memenuhi dua syarat: ia mempunyai bilangan bit set yang sama (1s dalam perwakilan binarinya) seperti integer yang diberikan, num2, dan XOR bitwise dengan integer lain yang diberikan, num1, diminimumkan.

Contoh 1:

• Input: num1 = 3, num2 = 5
• Output: 3
• Penjelasan: 3 (0011) dan 5 (0101) kedua-duanya mempunyai dua set bit. 3 XOR 3 = 0, iaitu nilai XOR minimum yang mungkin.

Contoh 2:

• Input: num1 = 1, num2 = 12
• Output: 3
• Penjelasan: 12 (1100) mempunyai dua set bit. 3 (0011) juga mempunyai dua set bit dan 3 XOR 1 = 2.

Kekangan:

• 1 ≤ num1, num2 ≤ 10⁹

Pendekatan Penyelesaian:

Kuncinya ialah strategi tamak. Untuk meminimumkan hasil XOR, kami ingin menjajarkan bit set x dengan bit set num1 sebanyak mungkin.

1. Kira Set Bit: Tentukan bilangan set bit dalam num2. Mari kita panggil ini targetBits.

2. Bina x: Mulakan x kepada 0. Lelaran melalui bit num1, bermula daripada bit yang paling ketara. Untuk setiap bit set dalam num1, jika kita belum mencapai targetBits lagi, tambah bit itu pada x. Jika kita sudah memenuhi syarat targetBits, langkau sedikit. Jika kita belum mencapai targetBits selepas memproses semua bit num1, tambah bit yang tinggal pada x, bermula dari bit yang paling tidak ketara.

3. Pulangan x: x yang dibina akan memenuhi syarat.

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

Kerumitan Masa dan Ruang:

• Kerumitan Masa: O(log N), dengan N ialah nilai maksimum num1 dan num2. Ini kerana kami mengulangi bit nombor.
• Kerumitan Ruang: O(1), ruang tambahan berterusan digunakan.

Penyelesaian yang dipertingkatkan ini menyediakan cara yang lebih jelas, cekap dan teguh untuk menyelesaikan masalah. Komen menerangkan logik pada setiap langkah.

Atas ialah kandungan terperinci Kurangkan XOR. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!