2429. 最小异或

🟠   🔖  贪心 位运算  🔗 力扣 LeetCode

题目

Given two positive integers num1 and num2, find the positive integer x such that:

• x has the same number of set bits as num2, and
• The value x XOR num1 is minimal.

Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

Example 1:

Input: num1 = 3, num2 = 5

Output: 3

Explanation:

The binary representations of num1 and num2 are 0011 and 0101, respectively.

The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.

Example 2:

Input: num1 = 1, num2 = 12

Output: 3

Explanation:

The binary representations of num1 and num2 are 0001 and 1100, respectively.

The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.

Constraints:

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

题目大意

给你两个正整数 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

解题思路

1. 统计二进制中 1 的个数

• 对 num1 和 num2，分别计算其二进制中 1 的个数：
  • count1 表示 num1 中的 1 的个数。
  • count2 表示 num2 中的 1 的个数。

2. 逐位调整 num1 的二进制

• 遍历 num1 的二进制表示（假设为 32 位整数）：
  • 如果 count1 > count2：从低位到高位寻找 1，将其置为 0，并减少 count1。
  • 如果 count1 < count2：从低位到高位寻找 0，将其置为 1，并增加 count1。
• 直到 count1 等于 count2，停止调整。

3. 返回调整后的结果

• 返回调整后的数字，它是满足条件的最小异或值。

复杂度分析

• 时间复杂度：O(1)，遍历所有 32 位，每次调整只需常数时间。
• 空间复杂度：O(1)，使用固定额外空间。

代码

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var minimizeXor = function (num1, num2) {
	let count1 = num1.toString(2).replace(/0/g, '').length; // num1 中 1 的个数
	let count2 = num2.toString(2).replace(/0/g, '').length; // num2 中 1 的个数

	let res = num1;

	for (let i = 0; i < 32; i++) {
		if (count1 > count2 && (res & (1 << i)) !== 0) {
			// 当前位是 1，清除该位
			res ^= 1 << i;
			count1--;
		} else if (count1 < count2 && (res & (1 << i)) === 0) {
			// 当前位是 0，设置为 1
			res ^= 1 << i;
			count1++;
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
421	数组中两个数的最大异或值		位运算 字典树 数组 1+	🟠	🀄️ 🔗
1707	与数组中元素的最大异或值		位运算 字典树 数组	🔴	🀄️ 🔗