力扣刷题笔记 #02 数位&二进制

本文最后更新于：2023年2月22日 下午

本文包含「数位&二进制」类型题中的：位运算技巧、与运算应用、异或应用。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

位运算技巧

常用技巧如下：

  • 末一置零：n & (n-1)，n &= n - 1;
  • 末零置一：n | (n+1)，n |= n + 1;
  • LowBit 运算：int t = n & (-n);
  • HighBit 运算：只能按位枚举，int t = 1<<31; while(!(n & t)) t>>=1;
  • 1 的个数：__builtin_popcount(n)

231. 2 的幂 (E)

题目描述：给定一个 int 值（可为负），判断该整数是否是 2 的幂次。

方法1：位运算，向右移位，当末位第一次出现 1 的时候，如果就是整数 1 则 true，复杂度为 \(O(k)\)。

方法2：末一置零，n & (n-1) 可以将二进制的最低位 1 移除，判断 n>0 && (n&(n-1))==0 即可。

方法3：Lowbit 运算，n & (-n) 可以仅保留二进制的最低位 1，判断 n>0 && (n&(-n))==n 即可。

坑点：等价运算符 == 的优先级高于位运算符，位运算必须加括号！

191. 位1的个数 (E)

题目描述：给出一个 32 位二进制整数，返回其二进制表达式中 1 的个数（也称汉明权重）。

方法1：位运算，向右以为，每次末位出现 1 的时候，答案增加，复杂度为 \(O(k)\)。

方法2：末一置零，多次进行末位清零直到整数归零，操作次数就是答案，复杂度为 \(O(k)\)。

方法3：二分法，C++ 中内置 __builtin_popcount(n) 实现，依次每 2、4、8、16 位取 1 累计，复杂度 \(O(\log k)\)。

1
2
3
4
5
6
7
8
unsigned __builtin_popcount(unsigned u) {
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

方法4：查表法，用长度 256 的数组存放每 8 位数对应的汉明权重，每次取末尾 8 位查表，移动 4 次累加，复杂度 \(O(1)\)。适合多次复用函数时用空间换时间。

338. 比特位计数 (E)

题目描述：给定整数 n，计算 0 到 n 的所有整数二进制表达式中 1 的个数，返回一个长度为 n + 1 的数组。

方法1：二分法，对每个数调用 __builtin_popcount(n)，复杂度 \(O(n\log k)\)。

方法2：查表法，用长度 256 的数组存放每 8 位数对应的汉明权重，每次进行查表，复杂度 \(O(n)\)。

方法3：DP，线性递推，遇到一个新数时可以转移到任何一个比它小的数，该数可以保证已经计算过，复杂度 \(O(n)\)。

  1. 转移到「末位清零」数字：\(dp[i]=dp[i \;\&\;(i-1)]+1\)
  2. 转移到「首位清零」数字，用一个变量 \(HighBit\) 记录 \(100\cdots00\)，即当 i&(i-1)==0 时更新依次，后面的一连串数字都可以转移：\(dp[i]=dp[i - HighBit]+1\)
  3. 转移到「右移一位」数字，将 \(i\) 右移一位，得到的数必定比原数小，根据最低位是否为 1 可以进行转移：\(dp[i]=dp[i >>1]+(i \;\&\;1)\)

2429. 最小 XOR (M)

题目描述：给定两个正整数 num1 和 num2，找出满足下述条件的整数 x：x 的置位数和 num2 相同且 x^num1 的值最小。

方法：贪心 + 位运算技巧，先用 __builtin_popcount(n) 统计出两个置位数，分类讨论，贪心地进行末一置零和末零置一，复杂度 \(O(k)\)。

  • cnt1 == cnt2，自身异或结果为零，返回 num1 即可。
  • cnt1 > cnt2，尽量将 num1 的高位 1 异或掉，因此答案要保留高位 1，将 num1 末一置零返回。使用 num1 &= num1 - 1。
  • cnt1 < cnt2，将 num1 异或完还有剩余，因此答案要把低位 0 异或掉，将 num1 末零置一返回。使用 num1 |= num1 + 1。

477. 汉明距离总和 (M)

题目描述：给定一个整数数组，要求计算数组中任意两两数字的汉明距离之和。

方法1：暴力，枚举每一对数，用 __bulitin_popcount(x^y) 获得汉明距离，时间复杂度 \(O(n^2\log k)\)。

方法2：逐位统计，不同二进制位的取值不会相互影响，同一二进制位上，如果某个元素取 \(1\)，则只需要统计其他元素有多少个 \(0\) 即可。换言之，假设该位上有 \(c\) 个 \(1\)、\(n-c\) 个 \(0\)，则距离之和为 \(n\cdot (n-c)\)。时间复杂度 \(O(n k)\)。

与运算应用

2419. 按位与最大的最长子数组 (M)

题目描述：给定一个数组，找出其中一个最长连续子数组，使其满足子数组中元素按位与的值最大，返回长度。

方法：直接遍历，题目可以转化为「数组中最大值连续出现的最大长度」，第一次遍历找出最大值，第二次遍历计算长度，复杂度 \(O(n)\)。

坑点：表面上是「最长连续子 XX」题，但是由于 a AND b <= min(a, b)，可以简化题目。

CF#721.A 最大的 k (M)

题目描述：给定 \(n\)，找到最大的 \(k\) 使得 \(n\&(n-1)\&\cdots\&k=0\)。

方法：脑筋急转弯，找到 \(n\) 的最高位 1（设为 \(t\)），显然要想将该位消去，至少得算到 \(2^t-1\)。而 \(2^t\&(2^t-1)=0\)，因此最大的 \(k\) 就是 \(2^t-1\)。时间复杂度 \(O(1)\)。

异或应用

136. 只出现一次的数字 (E)

题目描述：一个非空整数数组，除某个数字只出现了一次外，其余每个数字均出现两次。找出那个只出现一次的数字。

方法1：哈希表，记录出现过的数字和次数，最后再遍历哈希表，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：异或，对所有数字进行异或，由于异或具有交换律，两两消除最后剩下的就是答案。空间复杂度 \(O(1)\)。

137. 只出现一次的数字 II (M)

题目描述：一个非空整数数组，除某个数字只出现了一次外，其余每个数字均出现三次。找出那个只出现一次的数字。

方法1：哈希表，记录出现过的数字和次数，最后再遍历哈希表，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：分别考虑每个二进制位，对第 \(i\) 个二进制位进行累加，对于非答案的元素，必然是 \(3\) 个 \(0\) 或 \(3\) 个 \(1\)，则最后累加的结果必然是 \(3\) 的倍数，因此对 \(3\) 取余就能得到答案。时间复杂度 \(O(32n)\)，空间复杂度 \(O(1)\)。

方法3：利用逻辑电路并行化处理每个二进制位，每个二进制位有 \(\{0,1,2\}\) 三种可能，用两个寄存器 \(a,b\) 来存储 \(\{00,01,10\}\)，画出真值表后可以推出表达式。最后 \(b\) 就是答案。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

真值表包含 \(a,b,x\) 项，\(x\) 为下一个遇到的数字，结果为 \(a_{next}\) 和 \(b_{next}\)，分别算出表达式： \[ \begin{cases} a_{next}=\bar{a}bx+a\bar{b}\bar{x}\\ b_{next}=\bar{a}\bar{b}x+\bar{a}b\bar{x}=\bar{a}\left( b\oplus x \right)\\ \end{cases} \]

方法4：电路化简，观察方法 3 表达式，发现 \(a\) 的转移比 \(b\) 复杂，考虑先算出 \(b_{next}\)，再用其来计算 \(a_{next}\)，更为简便。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

坑点：方法 3 中的表达式右边都是上一刻的 \(a\) 和 \(b\)，必须用临时变量同时更新，也可以用 pair 和 tie 来操作。

扩展：此题中的「三次」可以修改为任意次数，只要对每个二进制位单独考虑即可。偶数次数也可以直接异或。

260. 只出现一次的数字 III (M)

题目描述：一个非空整数数组，恰有两个数字只出现了一次，其余每个数字均出现两次。找出那两个数字。

方法1：哈希表，记录出现过的数字和次数，最后再遍历哈希表，时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

方法2：异或，对所有数字进行异或，最后的异或和 \(x=x_1\oplus x_2\)，显然该结果不会为 \(0\)，否则两数应该相等。用 x＆－ｘ 得到最低位 \(1\)，显然 \(x_1\) 和 \(x_2\) 中该位的值不会相等。于是可以将所有数字根据该位的取值分为两类，各自进行异或和，得到的两个结果分别就是 \(x_1\) 和 \(x_2\)。

坑点：取 lowbit 时，要注意 INT_MIN 为 -2147483648，取反后将溢出，而其在二进制中表示为 \(100\cdots00\)，因此本身就可以作为 lowbit 使用。

287. 寻找重复数 (M)

题目描述：给定一个包含 \(n + 1\) 个整数的数组，其数字都在 \([1, n]\) 范围内，假设数组中有且仅有一个重复的整数，找出数组中重复的数字，要求空间复杂度 \(O(1)\)。

方法1：二分答案，定义 \(cnt[i]\) 表示数组中小于等于 \(i\) 的数的个数，假设重复数是 \(x\)，则 \([1,x-1]\) 里所有数都满足 \(cnt[i] \leq i\)；而 \([x,n]\) 里的所有数满足 \(cnt[i]>i\)。因此可以二分枚举 \(x\) 直到找到。时间复杂度 \(O(n\log n)\)。

方法2：二进制，预处理 \([1,n]\) 这 \(n\) 个数「每一位为 \(1\) 的个数之和」，如果当前数组的「每一位为 \(1\) 的个数之和」大于期望值，则说明重复数的这一位为 \(1\)。遍历每一位即可，时间复杂度 \(O(n \log n)\)。

方法3：抽象成环形链表寻找入口，快慢指针，先用 \(fast\) 和 \(slow\) 相遇，再用 \(pos\) 和 \(slow\) 相遇，时间复杂度 \(O(n)\)。

金典 17.19. 消失的两个数字 (H)

题目描述：给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字，找出这两个数字。

方法1：放入 1 到 N 所有的整数，求出异或和 \(x=x_1\oplus x_2\)，可以转化为找出只出现一次的两个数字。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法2：累加求出 \(x=x_1 + x_2\)，设 \(x_1 < x_2\)，则有 \(x/2\geqslant x_1\) ，将 \(1\) 到 \(x/2\) 的所有数累加看差值就可以找出 \(x_1\)，从而求出两个数字。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法3：累加求出 \(x_1 + x_2\) 和 \(x_1^{2}+x_2^{2}\)，从而求出 \(x_1 - x_2\)，联立即可。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

坑点：方法 3 计算平方和时可能溢出，需要用到计算技巧，包括 n * (n+1) / 2 * (2*n+1) / 3。

2401. 最长优雅子数组 (M)

题目描述：正整数组成的数组 nums 中找出最长连续子数组，使其满足子数组中所有元素 & 结果等于 0。

方法：滑动窗口 + 位运算，窗口内所有元素取 | 使二进制 1 位合并，右侧元素只需和整体进行 & 就能判断是否加入窗口，如果不能加入，则左侧元素需要弹出，使用 ^ 运算去除二进制 1 位。

算法笔记 > 力扣刷题
#Algorithm
力扣刷题笔记 #02 数位&二进制
https://hwcoder.top/LeetCode-Bitwise
作者
Wei He
发布于
2022年10月2日
许可协议