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

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 171 期的第 2 题，也是题目列表中的第 1318 题 -- 『或运算的最小翻转次数』

题目描述

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a | 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

官方难度

MEDIUM

解决思路

看完题目后，第一预感，要面对位操作啦。想到我之前的代码里其实已经用到了一些位运算，并且有小伙伴问到相关的问题。所以我们这里先简单说一些下面会用到的位操作，为后续代码中的使用作准备。

• & 即与操作。它的处理逻辑类似于逻辑运算符 &&，即 0 & 0 === 0、0 & 1 === 0、1 & 0 === 0、1 & 1 === 1。
• | 即或操作。它的处理逻辑类似于逻辑运算符 ||，即 0 | 0 === 0、0 | 1 === 1、1 | 0 === 1、1 | 1 === 1。
• >>> 即无符号右移，就是把该数的二进制表示的值向右移动一位，超出的那一位会被丢弃。例如 5 的二进制是 101，而 2 的二进制是 10，所以 5 >>> 1 === 2。
• << 即左移，就是把该数的二进制表示的值向左移动一位。例如 5 的二进制是 101，而 10 的二进制是 1010，所以 5 << 1 === 10。

更多的关于位操作、二进制、数在计算机中的存储方式等等，这里不做展开。未来的新坑里会详细提到。

那么现在我们看回这道题吧。题目的要求是，给定了三个数 a、b 和 c，期望是执行 a | b 操作后的结果即为 c。如果达不到的话，可以对 a 和 b 这两个数的二进制值进行翻转修改，即 0 变 1、1 变 0。返回需要最少需要进行翻转修改的次数。

首先要注意的是，这里的值都是指的二进制的值。然后结合我们上面说到过的 | 或操作的运算逻辑，我们可以整理一个表格，便于观察后续的处理方式。

通过这个表格，我们可以轻易的看出，只有 4 种情况需要进行翻转操作。那么为了得到最终的结果，我们只需要遍历二进制值的每一位，找出这 4 种情况进行计数即可。这里提供两种遍历的思路。

取最低位并修改值

如果我们想知道一个二进制值的第一位是 0 还是 1，我们应该怎么做呢？回看上面我们提到的位运算，会发现如何和 1 进行 & 与运算，那么当目标值是 0 的情况，会得到 0；当目标值是 1 的情况，会得到 1。借此我们就可以判断第一位究竟是 0 还是 1了。那么第二位呢，我们直接通过无符号右移这个操作把它变成第一位即可。

上述方案的具体流程如下：

1. 初始化计数为 0。

2. 如果 a 和 b 的第一位的或操作值不等于 c 的第一位：

   • 如果是需要翻转两个值的情况，则计数加 2。
   • 否则计数加 1。
3. 对三个数都进行右移 1 位的操作，并循环进行第 2 步。
4. 直到三个数都为 0 为止，返回计数结果。

基于以上流程，可以实现类似下面的代码：

const minFlips = (a, b, c) => {
  let ret = 0;
  while (a > 0 || b > 0 || c > 0) {
    if (((a & 1) | (b & 1)) !== (c & 1)) {
      ret += (a & 1) === 1 && (b & 1) === 1 ? 2 : 1;
    }
    a >>>= 1;
    b >>>= 1;
    c >>>= 1;
  }
  return ret;
};

通过掩码取出每一位

掩码这个概念可能不是那么常见，不过相信小伙伴们在设置 IP 的时候一定见过子网掩码这个字段。其实我们这里说的掩码就是一个用于进行预算的基准值，基于它和对应的运算可以把不必要的信息剔除掉，只保留我们需要的值。例如我们这里的需求其实就是想获取到这三个数的二进制的每一位值。

由于题目的条件种限制了三个数的范围为 [1, 10^9]，所以我们取个整数 32 位正好可以覆盖这个范围。具体流程如下：

1. 初始化掩码为 1，计数为 0。

2. 对于 a、b 和 c，用掩码取出对应的数值，并进行运算和比较：

   • 如果是需要翻转两个值的情况，则计数加 2。
   • 否则计数加 1。
3. 更新掩码的值，即左移 1 位。
4. 直到遍历完 32 位为止，返回计数结果。

基于以上流程，可以实现类似下面的代码：

const minFlips = (a, b, c) => {
  let ret = 0;
  let mask = 1;
  for (let i = 1; i < 32; ++i) {
    if (((a & mask) | (b & mask)) !== (c & mask)) {
      ret += (a & mask) === mask && (b & mask) === mask ? 2 : 1;
    }
    mask <<= 1;
  }
  return ret;
};

总结

这道题主要就是一些对于位运算的应用。本身题目内容并不难，不过需要一些二进制和位运算相关的知识。这部分的内容会比较偏向理论一些，所以这里暂时先不展开了。不过在这道题目的处理过程中，有个蛮有用的小方法，即我们罗列一些数据和结果，特别是当可能性不多的时候可以罗列所有可能性，往往会发现很有效果的方案。

相关链接

• Weekly Contest 171 题目列表
• 系列题解 repo
• 我的 segmentfault 专栏
• 我的知乎专栏