▲

3

▼

🔥 Жадный побитовый подход для решения задачи минимизации XOR

leetcoder, 15-01-2025 , 105

Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.

📜 Описание задачи

Дано два положительных числа num1 и num2. Нужно найти число x, такое что:

• Количество установленных битов в числе x равно количеству установленных битов в num2.
• Результат операции XOR между x и num1 минимален.

💡 Идея

Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.

✨ Детали подхода

1. Подсчёт установленных битов:
   • Используем метод count_ones, чтобы подсчитать количество установленных битов в числе num2.
2. Сохранение старших битов:
   • Проходим по битам num1 с самого старшего до младшего.
   • Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
3. Добавление младших битов:
   • После обработки старших битов переходим к младшим битам.
   • Добавляем неиспользованные биты до тех пор, пока количество установленных битов в результате не станет равным требуемому.
4. Возврат результата:
   • После формирования числа x возвращаем его.

📊 Асимптотика

• Временная сложность: O(1), так как обработка ограничена 32 битами.
• Пространственная сложность: O(1), так как используются только несколько переменных.

🧑‍💻 Исходный код

impl Solution {
    pub fn minimize_xor(num1: i32, num2: i32) -> i32 {
        // Calculate the number of set bits in num2
        let mut remaining_bits = num2.count_ones() as i32;
        let mut result = 0;

        // Step 1: Preserve as many high-order bits of num1 as possible
        let mut bit_mask = 1 << 30; // Start from the highest bit
        while remaining_bits > 0 && bit_mask > 0 {
            if num1 & bit_mask != 0 {
                result |= bit_mask; // Add the bit to the result
                remaining_bits -= 1; // Decrement remaining bits to set
            }
            bit_mask >>= 1; // Move to the next lower bit
        }

        // Step 2: Fill remaining bits with unset bits in num1 (from low to high)
        bit_mask = 1; // Start from the least significant bit
        while remaining_bits > 0 && bit_mask > 0 {
            if num1 & bit_mask == 0 {
                result |= bit_mask; // Add the bit to the result
                remaining_bits -= 1; // Decrement remaining bits to set
            }
            bit_mask <<= 1; // Move to the next higher bit
        }

        result
    }
}