题目1318:或运算的最小翻转次数

题目描述

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

解答技巧

本题需要用到一些位运算的知识:

• 对于十进制整数x,我们可以用x & 1得到x的二进制表示的最低位,它等价于x % 2:
  • 例如当x = 3时,x的二进制表示为11,x & 1的值为1;
  • 例如当x = 6时,x的二进制表示为110,x & 1的值为0。
• 对于十进制整数x,我们可以用x & (1 << k)来判断x二进制表示的第k位(最低位为第0位)是否为1。如果该表达式的值大于零,那么第k位为1:
  • 例如当x = 3时,x的二进制表示为11,x & (1 << 1) = 11 & 10 = 10 > 0,说明第1位为1;
  • 例如当x = 5时,x的二进制表示为101,x & (1 << 1) = 101 & 10 = 0,说明第1位不为1。

• 对于十进制整数x,我们可以用(x >> k) & 1得到x二进制表示的第k位(最低位为第0位)。如果x二进制表示的位数小于k,那么该表达式的值为零:

  • 例如当x = 3时,x的二进制表示为11,(x >> 1) & 1 = 1 & 1 = 1,说明第1位为1;
  • 例如当x = 5时,x的二进制表示为101,(x >> 1) & 1 = 10 & 1 = 0,说明第1位为0。
  • 例如当x = 6时,x的二进制表示为110,(x >> 3) & 1 = 0 & 1 = 0,说明第3位为0。

• 枚举+位运算

由于在或(OR)运算中,二进制表示的每一位都是独立的,即修改a或b二进制表示中的第i位,只会影响a OR b中第i位的值,因此我们可以依次枚举并考虑每一位。注意到a、b和c均小于10^9,它们的二进制表示最多有30位(包含31个二进制位的数最小为2^30 = 1073741824,已经大于10^9),因此我们只需要从低位到高位枚举这30位即可。

设a、b和c二进制表示的第i位分别为bit_a、bit_b和bit_c,根据bit_c的值,会有以下两种情况:

• 若bit_c的值为0,那么bit_a和bit_b必须都为0,需要的翻转次数为bit_a + bit_b;
• 若bit_c的值为1,那么bit_a和bit_b中至少有一个为1,只有当它们都为0时,才需要1次翻转;

我们将每一位的翻转次数进行累加,在枚举完所有位之后,就得到了最小翻转次数。

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(32):
            bit_a, bit_b, bit_c = (a >> i) & 1, (b >> i) & 1, (c >> i) & 1
            if bit_c == 0:
                ans += bit_a + bit_b
            else:
                ans += int(bit_a + bit_b) == 0
        return ans

复杂度分析:

时间复杂度:$O(\log C)$,其中C为常数,在本题中,C的值为10^9。$O(\log C)$等价于C的位数,也就是我们需要枚举的位数。

空间复杂度:O(1)。