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

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

解：

首先我们先了解二进制的计算，了解了这一点后这一题就迎刃而解了

首先呢我们需要明白一点：

• 只有当两个对应的二进制位都为 0 时，结果位为 0
• 如果两个对应的二进制位中至少有一个为 1，那么结果位为 1。

因此我们得出如下结论

当c某位为0时
1.a和b都为0 -> 不需要改变，操作数为0
2.a和b两位不同 -> 只需要改变其中一个即可，操作数为1
3.a和b都为1 -> 都需要改变，操作数为2

当c某位为1时：
1.a和b两位都为0，改变一个，操作数为1

因此我们得出如下代码

//==运算是错的，便于表示
int opt= 0;
if(c_bit == 0){
    if(a_bit == b_bit == 0){
        continue;
    }else if(a_bit != b_bit){
        opt++;
    }else if(a_bit == b_bit ==1){
        opt += 2;
    }

}else if(c_bit == 1){
    if(a_bit == b_bit == 0){
        opt ++;
    }else{
        continue;
    }
}

但是也没有精简一点的做法呢？有的兄弟，有的。
我们可以观察上面可以发现，当c==0时，二进制位相加就是操作数。

int opt= 0;
if(c_bit == 0){
    opt+= a_bit + b_bit;
}else{
    if(a_bit == 0 && b_bit ==0){
        opt++;
    }
}

好的，接下来我们来想想如何获取每个二进制位

首先我们需要明白两个操作：

使用位移操作 >> i 将 x 的二进制位右移 i 位，使第 i 位移动到最低位（第 0 位）

但位移后可能会残留高位数值，使用还需要按位与操作 & 1 来提取最低位的值（0 或 1）。

因为题目所说a最大为10^9，所以2^29 < 10^9 < 2^30 ，因此我们选择循环30次

int opt = 0;
for (int i = 0; i < 30; i++) {
    int cBit = (c >> i) & 1;
    int aBit = (a >> i) & 1;
    int bBit = (b >> i) & 1;

    if (cBit == 0) {
        opt += aBit + bBit; 
    } else {
        if (aBit == 0 && bBit == 0) {
            opt += 1; 
        }
    }
}