【位运算】5 道经典入门 LeetCode 位运算题整理
前言
最近学习位运算，一开始觉得很抽象、难理解，慢慢刷题后才发现：位运算其实就几个固定技巧，题目都是套路。这篇是我的学习整理，适合和我一样刚入门的同学。
6 个常用位运算核心技巧
这些技巧不用一下子全懂，做题时慢慢体会：
- 异或^：相同为0，不同为1，任何数和自己异或为0。作用：去重、查找只出现一次的数字
- 获取第 i 位：n & (1 << i)
- 消除最后一个1：n & (n - 1)。作用：统计 1 的个数、判断 2 的幂
- 保留最后一个1：n & -n
- 把第 i 位设为1：res |= (1 << i)
- 左移<<、右移>>：等价于乘 2 / 除 2
一、只出现一次的数字
题目
136. 只出现一次的数字 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
思路
利用异或抵消：
- 出现两次的数异或 → 0
- 0 异或答案 → 答案所以把数组全部异或一遍，剩下的就是只出现一次的数字。
代码
class Solution { public: int singleNumber(vector<int>& nums) { int len = nums.size(); int res = 0; for (int i = 0; i < len; i++) { res ^= nums[i]; } return res; } };二、颠倒二进制位
题目
190. 颠倒二进制位 颠倒给定的 32 位有符号整数的二进制位。
这道题在 LeetCode 190.颠倒二进制位 | 从暴力解法到位运算魔法-ZEEKLOG博客 中有详细讲解。
思路
一位一位取出来，再一位一位放到结果里，相当于把二进制 “倒过来”。
代码
class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for (uint32_t i = 0; i < 32; i++) { uint32_t bit = n >> i & 1; // 从右往左取n的每一位数字 res <<= 1; // res整体往左挪一位，空出最右边的位置 res |= bit; // 将取出的数字放在res的最右边 } return res; } };三、位1的个数
题目
191. 位1的个数 给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
思路
技巧：n & (n-1) 会消除最后一个 1
消除几次，就有几个 1。
代码
class Solution { public: int hammingWeight(int n) { int res = 0; while (n) { n &= n - 1; // 消除最后一个1 res++; // 消除次数=1的个数 } return res; } };四、2的幂
题目
231. 2 的幂 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
思路
2的幂的二进制特点：有且只有一个1
消除最后一个 1 后一定变成 0，同时要保证 n > 0
代码
class Solution { public: bool isPowerOfTwo(int n) { if (n <= 0) { // 只有正整数才能为2的幂次方 return false; } n &= (n - 1); // 消除最后一个1 return n == 0; // 2的幂次方只有一个1，消除之后n=0 } };五、丢失的数字
题目
268. 丢失的数字 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
思路
依旧是异或去重：可以使res（初始为n）异或0~n-1，同时异或数组的元素，最终这个数的结果就是丢失的数字。因为数组中的存在的数字被异或了两次，只有丢失的数字只被异或了一次。
代码
class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); int res = n; for (int i = 0; i < n; i++) { res ^= i;// 异或0~n-1 res ^= nums[i];// 异或数组中的数字 } return res; } };学习小结
位运算刚学的时候确实不太习惯，但刷完这几道题发现：题目考来考去，都是那几个固定技巧。
- 看到重复、消失、只出现一次 → 想异或
- 看到统计 1、2 的幂 → 想
n & (n-1) - 看到二进制翻转 → 想移位 + 取位
继续多练几道，应该就能越来越熟练了。
