今日题目

https://leetcode.com/problems/minimize-xor/description/

异或（XOR）

下图是 $XOR$ 的真值表： image.png 从图中可以看出：若 A 与 B 相同，则 $A\space XOR\space B = 0$；否则，$A\space XOR\space B = 1$。

解题思路

  • 题目第一个条件"相同数量的置位"，指的是"数字中比特位 1 的数量相同"。

  • 原因在于：一个数中 0 的个数可以无限多，而比特位 1 的个数是有限的。

  • 因此，我们需要统计 number2 中 1 的个数。

  • 根据 $XOR$ 真值表，要让某一位在异或后变为 0，需要在结果数中该位也置 1，与 number1 中对应位的 1 抵消。

  • 为使结果最小，应优先从高位向低位消除 number1 中的 1。

  • 若 number2 中 1 的个数多于 number1，则需要在结果中额外补充 1。

  • 为使结果最小，额外补充的 1 应从低位向高位填入。

算法步骤

  1. 使用 $bit_count()$ 函数统计 num2 中 1 的个数。
  2. 从高位到低位遍历，优先消除 number1 中的 1。
  3. 从低位到高位遍历，补充剩余所需的 1。

复杂度分析

  • 时间复杂度：$O(log_2(N))$，N 为输入数字的大小。

  • 空间复杂度：$O(1)$，仅使用若干变量。

代码

class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        cnt,ans = num2.bit_count(), 0
        for i in range(31, -1, -1):
            if cnt > 0 and (num1 & (1 << i)) > 0:
                ans += (1 << i)
                cnt -= 1
        
        for i in range(31):
            if cnt > 0 and (ans & (1 << i)) == 0:
                ans += (1 << i)
                cnt -= 1
        
        return ans

image.png