README.md

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

English Version

题目描述

给你三个正整数 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 对应二进制位，进行比较计数。

Python3

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(31):
            x, y, z = (a >> i) & 1, (b >> i) & 1, (c >> i) & 1
            if (x | y) == z:
                continue
            if x == 1 and y == 1 and z == 0:
                ans += 2
            else:
                ans += 1
        return ans

Java

class Solution {
    public int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int x = (a >> i) & 1, y = (b >> i) & 1, z = (c >> i) & 1;
            if ((x | y) == z) {
                continue;
            }
            if (x == 1 && y == 1 && z == 0) {
                ++ans;
            }
            ++ans;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int x = (a >> i) & 1, y = (b >> i) & 1, z = (c >> i) & 1;
            if ((x | y) == z) continue;
            if (x == 1 && y == 1 && z == 0) ++ans;
            ++ans;
        }
        return ans;
    }
};

Go

func minFlips(a int, b int, c int) int {
	ans := 0
	for i := 0; i < 31; i++ {
		x, y, z := (a>>i)&1, (b>>i)&1, (c>>i)&1
		if (x | y) == z {
			continue
		}
		if x == 1 && y == 1 && z == 0 {
			ans++
		}
		ans++
	}
	return ans
}

...