或运算的最小翻转次数

难度: Medium

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

Submission

运行时间: 16 ms

内存: 16.0 MB

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

        sums = 0

        a_bin, b_bin, c_bin = list(bin(a)[2:]), list(bin(b)[2:]), list(bin(c)[2:])

        n = max(len(c_bin), len(b_bin), len(a_bin))

        for i in range(n - len(a_bin)):
            a_bin.insert(0, '0')
        for i in range(n - len(b_bin)):
            b_bin.insert(0, '0')
        for i in range(n - len(c_bin)):
            c_bin.insert(0, '0')

        i = n - 1

        while i >= 0:
            if (int(a_bin[i]) | int(b_bin[i])) != int(c_bin[i]):
                if c_bin[i] == '0':
                    sums += int(a_bin[i]) + int(b_bin[i])
                elif c_bin[i] == '1':
                    sums += 1
            i -= 1
        
        return sums

Explain

题解的思路是通过逐位比较a、b和c的二进制表示，来确定需要进行多少次翻转以使得a OR b等于c。首先将a、b、c转换为二进制形式并补齐为相同长度，然后从最高位向最低位逐位进行比较。如果当前位的结果c不等于a或b的按位或结果，需要进行翻转。如果c的当前位是0，那么a和b的相应位都必须翻转为0；如果c的当前位是1，那么a和b中至少有一个位必须翻转为1。

时间复杂度: O(1)

空间复杂度: O(1)

# class containing the method to find minimum flips
class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        # Initialize counter for flips
        flips = 0

        # Convert numbers to binary strings and pad to the maximum length
        a_bin, b_bin, c_bin = bin(a)[2:], bin(b)[2:], bin(c)[2:]
        max_length = max(len(a_bin), len(b_bin), len(c_bin))
        a_bin = a_bin.zfill(max_length)
        b_bin = b_bin.zfill(max_length)
        c_bin = c_bin.zfill(max_length)

        # Iterate over each bit from the least significant to most significant
        for i in range(max_length-1, -1, -1):
            a_bit, b_bit, c_bit = int(a_bin[i]), int(b_bin[i]), int(c_bin[i])
            # Determine necessary flips based on the target bit in c
            if (a_bit | b_bit) != c_bit:
                if c_bit == 0:
                    # Both bits must be turned off
                    flips += a_bit + b_bit
                elif c_bit == 1:
                    # At least one bit must be turned on
                    flips += 1

        # Return the total number of flips required
        return flips

Explore

这是因为当c的位为1时，至少需要确保a或b中的一个对应位为1（如果都是0，则只需翻转其中一个即可），因此至少增加1次翻转。而当c的位为0时，需要确保a和b的对应位都必须为0，所以如果a和b的这一位原来都是1或其中一个是1，就需要翻转一次或两次，因此翻转次数可能是1次或2次。

实际上，无论是从最低位到最高位还是从最高位到最低位遍历，算法的逻辑并不会改变，因为每一位的翻转决策都是独立的，不影响其他位的状态。示例中从最低位向最高位遍历是一种常见的做法，但从最高位向最低位同样有效。这里的选择可能是基于习惯或者是为了与某些特定的编程环境或库的操作保持一致。

如果a、b、c的二进制长度不一，则在不补齐的情况下，较短的数字在高位的缺失部分默认为0，这可能导致错误的翻转决策。例如，如果c的高位是1而a和b的对应高位不存在（即默认为0），那么就需要对这些默认为0的位进行翻转操作。通过将所有数字补齐到相同的长度，我们能够确保在比较每一位时不会忽略这些隐含的0，从而正确地计算出必要的翻转次数。补齐长度是为了在逻辑上简化实现，使每一位都能显式地参与运算。