【位运算】最小 XOR【力扣第 313 场周赛】

题目

6194. 最小 XOR

---

给你两个正整数 num1 和 num2 ，找出满足下述条件的整数 x ：

• x 的置位数和 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

解题

方法一：位运算

思路

首先求出 nums2 的“置位数”(cnt)，也就是 nums2 的汉明权重，计算方法见：【位运算】位1的个数。

现在我们就有 cnt 个 $1$ 用来组成二进制形式的 x，接下来要使 $x \oplus num1$ 的值最小，就应该尽量消掉 nums1 高位的 $1$ ，考虑三种情况：

• 当 $x 的置位数 < nums1 的置位数$：从高位开始，尽量让 nums1 中有 $1$ 的位，x 也有。
• 当 $x 的置位数 = nums1 的置位数$：nums1 中有 $1$ 的位，x 也应该有，此时 $x \oplus num1 = 0$ 最小。
• 当 $x 的置位数 > nums1 的置位数$：nums1 中有 $1$ 的位，x 也应该有，但是要把剩下的 $1$ 都用完，所以从低位开始填充 $1$ 以使 $x \oplus num1$ 尽量小。

例如：$num1 = 110010_{(2)}, num2 = 11110_{(2)}$

代码

class Solution {
    public int minimizeXor(int num1, int num2) {
        // 拿到num2的“置位数”
        int cnt = hammingWeight(num2), x = 0;
        // 在1的数量够用的情况下从高位开始把num1中的每一位1复制到ans中
        for (int i = 29; i >= 0 && cnt > 0; --i) {
            int mask = 1 << i;
            if ((num1 & mask) != 0) {
                x |= mask;
                --cnt;
            }
        }
        // 把多余的1从低位开始填充到x中
        for (int i = 0; i <= 29 && cnt > 0; ++i) {
            int mask = 1 << i;
            if ((x & mask) == 0) {
                x |= mask;
                --cnt;
            }
        }
        return x;
    }

    // 计算汉明权重
    int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            n &= n - 1;
            cnt++;
        }
        return cnt;
    }
}