1318. 或运算的最小翻转次数

🟠   🔖  位运算  🔗 力扣 LeetCode

题目

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5

Output: 3

Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

Input: a = 4, b = 2, c = 7

Output: 1

Example 3:

Input: a = 1, b = 2, c = 3

Output: 0

Constraints:

• 1 <= a <= 10^9
• 1 <= b <= 10^9
• 1 <= c <= 10^9

题目大意

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

示例 1：


输入： a = 2, b = 6, c = 5

输出： 3

解释： 翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2：

输入： a = 4, b = 2, c = 7

输出： 1

示例 3：

输入： a = 1, b = 2, c = 3

输出： 0

提示：

• 1 <= a <= 10^9
• 1 <= b <= 10^9
• 1 <= c <= 10^9

解题思路

逐位比较：对 a、b 和 c 的二进制表示，从最低位到最高位逐位比较，判断需要翻转的次数。

按位规则：

• 如果 c 的当前位是 1，则 a, b 必须至少有一位是 1：
  • 如果当前位的 a 和 b 都是 0，需要翻转其中一个为 1，翻转次数为 1。
• 如果 c 的当前位是 0，则 a, b 必须都是 0：
  • 如果当前位的 a 是 1 或 b 是 1，翻转次数为 a 和 b 中的 1 位数之和。

1. 初始化变量 flips 用于记录翻转次数。
2. 使用循环，逐位取出 a、b、c 的当前位，直到所有位都处理完。
3. 根据 c 的当前位是 0 或 1，判断翻转的需求：
   • 若 c 位为 1，检查 a_i 和 b_i 是否需要调整；
   • 若 c 位为 0，统计 a_i 和 b_i 中的 1，累加到翻转次数。
4. 将 a、b 和 c 右移一位，继续处理下一位。
5. 返回总翻转次数。

复杂度分析

• 时间复杂度：O(log(max(a, b, c)))，循环最多运行 O(log(max(a, b, c))) 次，因为每次循环右移一位。
• 空间复杂度：O(1)，使用了常数额外空间用于存储变量。

代码

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var minFlips = function (a, b, c) {
	let flips = 0;
	while (a > 0 || b > 0 || c > 0) {
		// 提取当前最低位
		const bitA = a & 1;
		const bitB = b & 1;
		const bitC = c & 1;

		if (bitC === 0) {
			// 如果 c 的当前位是 0，则 a 和 b 的当前位都必须是 0
			flips += bitA + bitB;
		} else {
			// 如果 c 的当前位是 1，则至少有一个 a 或 b 的当前位为 1
			if (bitA === 0 && bitB === 0) {
				flips += 1;
			}
		}

		// 右移一位，处理下一位
		a >>= 1;
		b >>= 1;
		c >>= 1;
	}
	return flips;
};

相关题目

题号	标题	题解	标签	难度	力扣
2220	转换数字的最少位翻转次数		位运算	🟢	🀄️ 🔗