⚡Flashcard Drill➔
NeetCode #879LC-2429MediumBit Manipulation
← Back to All Problems

#879 · #2429 · Minimize XOR(最小异或)

📌 Problem Statement & Constraints

Given two positive integers num1 and num2, find a positive integer x that has exactly the same number of set bits as num2 and minimises num1 XOR x. Return x. Constraints: 1 <= num1, num2 <= 10^9.

💡 Core Algorithmic Approaches

  1. The number of set bits in x is fixed at popcount(num2), so the only freedom is which positions to set.
  2. To minimise num1 ^ x, set bits where num1 already has them, starting from the most significant position.
  3. Copy num1's set bits into x from the top down until the bit budget is exhausted.
  4. If bits remain, place them at the lowest unset positions, which contribute least to the XOR.

💻 Benchmark Python3 Implementation

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        need = bin(num2).count("1")     # x must have exactly this many set bits
        x = 0
        # first reuse the set bits of num1 from the top down
        for b in range(31, -1, -1):
            if need and num1 >> b & 1:
                x |= 1 << b
                need -= 1
        # any remaining bits go to the lowest free positions
        b = 0
        while need:
            if not (x >> b & 1):
                x |= 1 << b
                need -= 1
            b += 1
        return x

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(32) = O(1): a constant number of bit positions.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Setting the lowest bits first: that maximises num1 ^ x; matching the highest set bits of num1 first is what minimises it.
  • Using popcount(num1) as the budget: x needs exactly popcount(num2) set bits.
  • Forgetting the leftover bits: when popcount(num2) exceeds the bits matched from num1, the rest must be placed somewhere.
  • Placing leftover bits at the top: they would inflate the XOR; the lowest free positions contribute least.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems