侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-10-02 / 0 评论 / 0 点赞 / 58 阅读 / 708 字 / 正在检测是否收录...

题目

6194. 最小 XOR


给你两个正整数 num1num2 ,找出满足下述条件的整数 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的个数

现在我们就有 cnt11 用来组成二进制形式的 x,接下来要使 xnum1x \oplus num1 的值最小,就应该尽量消掉 nums1 高位的 11 ,考虑三种情况:

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

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

动画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;
    }
}
0

评论区