XOR minimieren

2429. XOR minimieren

Schwierigkeit:Mittel

Themen:Gierig, Bit-Manipulation

Dieses Problem stellt Sie vor die Herausforderung, eine positive ganze Zahl x zu finden, die zwei Bedingungen erfüllt: Sie hat die gleiche Anzahl gesetzter Bits (1 in ihrer Binärdarstellung) wie eine gegebene ganze Zahl num2. und sein bitweises XOR mit einer anderen gegebenen Ganzzahl, num1, wird minimiert.

Beispiel 1:

• Eingabe: num1 = 3, num2 = 5
• Ausgabe: 3
• Erklärung: 3 (0011) und 5 (0101) haben beide zwei gesetzte Bits. 3 XOR 3 = 0, was der minimal mögliche XOR-Wert ist.

Beispiel 2:

• Eingabe: num1 = 1, num2 = 12
• Ausgabe: 3
• Erklärung: 12 (1100) hat zwei gesetzte Bits. 3 (0011) hat auch zwei gesetzte Bits und 3 XOR 1 = 2.

Einschränkungen:

• 1 ≤ num1, num2 ≤ 10⁹

Lösungsansatz:

Der Schlüssel ist eine gierige Strategie. Um das XOR-Ergebnis zu minimieren, möchten wir die gesetzten Bits von x so weit wie möglich an den gesetzten Bits von num1 ausrichten.

1. Anzahl gesetzter Bits: Bestimmen Sie die Anzahl der gesetzten Bits in num2. Nennen wir es targetBits.

2. Konstruiere x: Initialisiere x auf 0. Iteriere durch die Bits von num1, beginnend mit dem höchstwertigen Bit. Für jedes gesetzte Bit in num1, wenn wir targetBits noch nicht erreicht haben, fügen Sie dieses Bit zu x hinzu. Wenn wir die targetBits-Anforderung bereits erfüllt haben, überspringen Sie den Teil. Wenn wir nach der Verarbeitung aller Bits von targetBits noch nicht num1 erreicht haben, fügen Sie die verbleibenden Bits zu x hinzu, beginnend mit dem niedrigstwertigen Bit.

3. Gib x zurück: Das konstruierte x erfüllt die Bedingungen.

PHP-Implementierung:

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

Zeitliche und räumliche Komplexität:

• Zeitkomplexität: O(log N), wobei N der Maximalwert von num1 und num2 ist. Das liegt daran, dass wir die Bits der Zahlen durchlaufen.
• Raumkomplexität: O(1), konstanter zusätzlicher Raum wird verwendet.

Diese verbesserte Lösung bietet eine klarere, effizientere und robustere Möglichkeit, das Problem zu lösen. Die Kommentare erläutern die Logik bei jedem Schritt.

Das obige ist der detaillierte Inhalt vonXOR minimieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!