Medium

题目描述

给定两个正整数 num1 和 num2，找到一个正整数 x 使得：

  • x 的置位数（二进制中1的个数）与 num2 相同
  • x XOR num1 的值最小

注意：XOR 是按位异或运算。

返回整数 x。测试用例保证 x 是唯一确定的。

整数的置位数是指其二进制表示中1的个数。

示例 1：

输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101。
整数 3 与 num2 具有相同的置位数，且 3 XOR 3 = 0 是最小值。

示例 2：

输入：num1 = 1, num2 = 12
输出：3
解释：
num1 和 num2 的二进制表示分别是 0001 和 1100。
整数 3 与 num2 具有相同的置位数，且 3 XOR 1 = 2 是最小值。

约束条件：

  • 1 <= num1, num2 <= 10^9

解题思路

这道题的核心思想是：要使 x XOR num1 最小，我们应该让 x 与 num1 尽可能相似。

解题思路：

  1. 统计置位数：首先计算 num2 的置位数，这就是 x 必须拥有的置位数。

  2. 贪心策略：为了最小化异或值，我们希望 x 和 num1 的相同位置都是1（这样异或结果为0）。因此：

    • 优先保留 num1 中已经是1的位
    • 如果保留的1不够，就在 num1 为0的最低位位置补1
    • 如果保留的1太多，就去掉 num1 中最低位的1

  3. 具体算法：

    • 先统计 num1 和 num2 的置位数
    • 如果 num1 的置位数等于 num2 的置位数，直接返回 num1
    • 如果 num1 的置位数大于 num2 的置位数，从最低位开始清除多余的1
    • 如果 num1 的置位数小于 num2 的置位数，在最低的0位设置为1

这种贪心策略保证了异或值最小，因为我们优先保持高位相同，只在低位进行调整。

推荐解法：使用位操作的贪心算法，时间复杂度O(log n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int target_bits = __builtin_popcount(num2);
        int current_bits = __builtin_popcount(num1);
        int result = num1;
        
        if (current_bits > target_bits) {
            // 需要清除多余的1位，从最低位开始
            int to_clear = current_bits - target_bits;
            for (int i = 0; i < 32 && to_clear > 0; i++) {
                if (result & (1 << i)) {
                    result &= ~(1 << i);
                    to_clear--;
                }
            }
        } else if (current_bits < target_bits) {
            // 需要添加1位，在最低的0位设置
            int to_add = target_bits - current_bits;
            for (int i = 0; i < 32 && to_add > 0; i++) {
                if ((result & (1 << i)) == 0) {
                    result |= (1 << i);
                    to_add--;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        target_bits = bin(num2).count('1')
        current_bits = bin(num1).count('1')
        result = num1
        
        if current_bits > target_bits:
            # 需要清除多余的1位，从最低位开始
            to_clear = current_bits - target_bits
            for i in range(32):
                if to_clear == 0:
                    break
                if result & (1 << i):
                    result &= ~(1 << i)
                    to_clear -= 1
        elif current_bits < target_bits:
            # 需要添加1位，在最低的0位设置
            to_add = target_bits - current_bits
            for i in range(32):
                if to_add == 0:
                    break
                if (result & (1 << i)) == 0:
                    result |= (1 << i)
                    to_add -= 1
        
        return result

public class Solution {
    public int MinimizeXor(int num1, int num2) {
        int targetBits = CountBits(num2);
        int currentBits = CountBits(num1);
        int result = num1;
        
        if (currentBits > targetBits) {
            // 需要清除多余的1位，从最低位开始
            int toClear = currentBits - targetBits;
            for (int i = 0; i < 32 && toClear > 0; i++) {
                if ((result & (1 << i)) != 0) {
                    result &= ~(1 << i);
                    toClear--;
                }
            }
        } else if (currentBits < targetBits) {
            // 需要添加1位，在最低的0位设置
            int toAdd = targetBits - currentBits;
            for (int i = 0; i < 32 && toAdd > 0; i++) {
                if ((result & (1 << i)) == 0) {
                    result |= (1 << i);
                    toAdd--;
                }
            }
        }
        
        return result;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var minimizeXor = function(num1, num2) {
    const countBits = (n) => {
        let count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    };
    
    const targetBits = countBits(num2);
    let x = 0;
    let bitsSet = 0;
    
    // First, set bits where num1 has bits set (from most significant to least)
    for (let i = 30; i >= 0 && bitsSet < targetBits; i--) {
        if ((num1 >> i) & 1) {
            x |= (1 << i);
            bitsSet++;
        }
    }
    
    // If we need more bits, set them from least significant positions
    for (let i = 0; i <= 30 && bitsSet < targetBits; i++) {
        if (!((x >> i) & 1)) {
            x |= (1 << i);
            bitsSet++;
        }
    }
    
    return x;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)最多遍历32位，其中n为输入数字的最大值
空间复杂度O(1)只使用常数额外空间

相关题目