前言
最近学习位运算，一开始觉得很抽象、难理解，慢慢刷题后才发现：位运算其实就几个固定技巧，题目都是套路。这篇是我的学习整理，适合和我一样刚入门的同学。
6 个常用位运算核心技巧
这些技巧不用一下子全懂，做题时慢慢体会：
一、只出现一次的数字
题目
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.颠倒二进制位 | 从暴力解法到位运算魔法-CSDN博客 中有详细讲解。
思路
一位一位取出来，再一位一位放到结果里，相当于把二进制 “倒过来”。
代码
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)
- 看到二进制翻转 → 想移位 + 取位
继续多练几道，应该就能越来越熟练了。
