- 优先级坑：位运算优先级 低于加减，判断条件必须加括号：(n & 1) == 1，不可写 n & 1 == 1
- 移位溢出坑：int类型左移超过31位会溢出，大数建议用long long
- 负数右移坑：负数右移补1，不要对负数做右移整除运算
- lowbit仅正数有效：n为负数时n&-n失效，必须保证操作数为正
- 极致提速：位运算为CPU原生指令，比算术运算快数倍，解决大数据超时问题；
- 极致压缩：用整数二进制存储状态，大幅节省数组空间；
- 代码极简：复杂逻辑一行代码实现，减少bug、简化思路；
- 必考考点：GESP6-7级、CSP-J/S、NOIP每年必考，填空、选择、编程大题全覆盖。
位运算在信息奥赛中的各种巧妙用法（全覆盖、竞赛专用）
位运算是信息奥赛（GESP/CCF/CSP/NOIP）的核心高分技巧，基于二进制底层运算，速度远超普通加减乘除、取模运算，代码极简、效率极高。多数优化题、暴力卡常题、状态压缩题，不用位运算会超时，用位运算可满分。
本文汇总竞赛中所有必考、常用、巧妙的位运算用法，附带原理、模板、适用场景，无废话、纯竞赛干货。
一、前置：6种基础位运算（竞赛核心）
所有巧妙用法均基于以下6种运算，熟记规则是解题基础：
|
运算符
|
名称
|
运算规则（二进制）
|
竞赛核心特点
|
|
|
按位与
|
两位同为1则为1，否则为0
|
清零、取位、判断奇偶
|
|
|
|
按位或
|
两位有1则为1，全0为0
|
置1、状态合并
|
|
^
|
按位异或
|
两位不同为1，相同为0
|
翻转、交换、去重、找唯一数
|
|
~
|
按位取反
|
0变1，1变0
|
快速取反、配合移位使用
|
|
<<
|
左移
|
二进制整体左移，右侧补0
|
快速乘2、开辟状态位
|
|
>>
|
右移
|
二进制整体右移，左侧补符号位
|
快速除2、二分压缩
|
二、基础巧妙用法（入门必考，GESP/普及组）
1. 极速奇偶判断（替代 n%2）
原理：二进制末尾为1是奇数，0是偶数，只需判断最后一位
位运算模板：
if(n & 1) // 奇数
if(!(n & 1)) // 偶数
优势：位运算速度远快于取模运算，大数据量下可避免超时，竞赛通用最优写法。
2. 快速乘2、除2（替代 *2 /2）
原理：二进制左移一位等价×2，右移一位等价÷2（向下取整）
n << 1; // n * 2
n >> 1; // n / 2 （整数向下取整）
适用场景：二分答案、倍增算法、树的层序遍历、数值快速缩放。
3. 交换两个整数（无需临时变量）
原理：异或性质：a^a=0，a^0=a，异或满足交换律、结合律
a ^= b;
b ^= a;
a ^= b;
特点：不占用额外空间，代码极简，竞赛小众但高级写法。
4. 快速判断2的整数次幂
原理：2的幂二进制只有1个1，如1(1)、2(10)、4(100)，n&(n-1)可清零唯一的1，结果为0
bool isPow2(int n){
return n && !(n &
(n-1));
}
注意：必须加n!=0判断，避免0误判为2的幂。
5. 快速清零二进制最后一个1
模板：n = n & (n - 1)
示例：6(110) & 5(101) = 4(100)，末尾1被清零
用途：统计二进制中1的个数、状态遍历、子集枚举。
三、中级巧妙用法（普及组核心，高频考点）
1. 统计二进制中1的个数（最优解法）
常规循环取模效率低，位运算极速清零统计，时间复杂度仅O(二进制1的个数)
int countOne(int n){
int cnt = 0;
while(n){
n &= n-1; // 每次消掉最后一个1
cnt++;
}
return cnt;
}
2. 提取二进制最后一个1（lowbit操作）
竞赛神级操作，必考
模板：lowbit = n & -n
原理：利用负数补码特性，精准保留二进制最后一个1，其余位清零
示例：6(110) lowbit=2(10)，8(1000) lowbit=8(1000)
核心用途：树状数组（BIT）底层核心、二进制拆分、子集遍历。
3. 翻转二进制指定位
模板：n ^= (1 << k)
作用：将n的第k位二进制（从0开始计数）0变1、1变0
场景：状态压缩、开关问题、棋盘翻转问题。
4. 判断第k位二进制是否为1
// 判断n的第k位是否为1
if(n & (1 << k))
状态压缩、权限判断、二进制拆分最常用写法。
5. 将第k位二进制强制置1/置0
n |= (1 <<
k); // 第k位 置1
n &= ~(1 << k); // 第k位 置0
四、高级竞赛用法（提高组/省赛核心）
1. 异或找唯一数（经典真题模型）
题目模型：数组中所有数出现两次，仅有一个数出现一次，求这个数
原理：相同数异或为0，0异或任意数为其本身，全员异或即可得到唯一数
int res = 0;
for(int i=0;i<n;i++) res ^= a[i];
cout << res;
时间复杂度O(n)，空间O(1)，最优解法，无替代方案。
2. 状态压缩DP（竞赛压轴核心）
利用一个整数的二进制位存储多个状态，极大压缩空间、优化时间，是棋盘、背包、子集问题的核心解法。
核心思想：int有32位，可存储32个布尔状态，替代二维数组存状态。
常用模板：遍历一个状态的所有子集
// 遍历mask的所有子集
for(int s = mask; s; s = (s-1) & mask)
适用题型：铺瓷砖、哈密尔顿路径、子集求和、状态转移DP。
3. 快速幂位运算优化
普通幂运算循环太慢，位运算拆分指数，时间复杂度从O(n)降为O(log
n)
long long qpow(long long
a,long long b){
long long res = 1;
while(b){
if(b & 1) res = res * a; //
二进制当前位为1，乘入结果
a = a * a;
b >>= 1; // 右移拆分指数
}
return res;
}
五、竞赛位运算避坑要点（扣分易错点）
六、竞赛位运算核心价值总结