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
- The number of set bits in
xis fixed atpopcount(num2), so the only freedom is which positions to set. - To minimise
num1 ^ x, set bits wherenum1already has them, starting from the most significant position. - Copy
num1's set bits intoxfrom the top down until the bit budget is exhausted. - 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 ofnum1first is what minimises it. - Using
popcount(num1)as the budget:xneeds exactlypopcount(num2)set bits. - Forgetting the leftover bits: when
popcount(num2)exceeds the bits matched fromnum1, 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.