Leetcode: 5308. 或运算的最小翻转次数

题目描述

给你三个正整数 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对应位不等,且此时a和b对应位都为1,则要改变两次,否则只要改变1次;

代码

class Solution {
public:
    int minFlips(int a, int b, int c) {
        std::bitset<sizeof(int)*8> a_bit(a);
        std::bitset<sizeof(int)*8> b_bit(b);
        std::bitset<sizeof(int)*8> c_bit(c);
        int count = 0;
        for (size_t i = 0; i < sizeof(int)*8; i++)
        {
            if((a_bit | b_bit) == c_bit ){
                break;
            }else
            {
                if((a_bit[i] | b_bit[i]) != c_bit[i]){
                    if(a_bit[i] == 1 && b_bit[i] == 1){
                        a_bit[i] = !a_bit[i];
                        b_bit[i] = !b_bit[i];
                        count += 2;
                    }else{
                        a_bit[i] = !a_bit[i];
                        count++;
                    }
                }
            }
        }
        return count;
    }
};
打赏作者