写在前面位运算是算法竞赛中的隐形加速器它不仅能将O ( n ) O(n)O(n)优化到O ( 1 ) O(1)O(1)更是状态压缩、树状数组等高级算法的基石。本文基于蓝桥杯官方课程从二进制底层原理到竞赛实战带你彻底掌握位运算一、位运算基础二进制世界的六大法则位运算直接对二进制位进行操作是CPU最底层的运算方式速度极快。1.1 与运算—— “有0则0全1为1”xyx y000010100111实例6 11 20110 (6) 1011 (11) -------- 0010 (2)1.2 或运算|—— “有1则1全0为0”xyx | y000011101111实例6 | 11 150110 (6) | 1011 (11) -------- 1111 (15)1.3 异或运算^—— “相同为0不同为1” ⭐重点xyx ^ y000011101110核心性质竞赛必考交换律x ^ y y ^ x结合律x ^ (y ^ z) (x ^ y) ^ z自反性x ^ x 0自己异或自己等于0零元素x ^ 0 x逆运算若x ^ y z则z ^ y x实例6 ^ 11 130110 (6) ^ 1011 (11) -------- 1101 (13)1.4 取反~—— “1变00变1”实例~6 -7在32位系统中注意符号位~ 0000 0110 (6) -------- 1111 1001 (-7, 补码表示)注意Python中整数无限精度~x -x-11.5 左移—— “乘以2的幂”二进制位向左移动右侧补0。每左移1位 乘以2实例5 3 40原数 0000 0101 (5) 左移3位0010 1000 (40) # 相当于 5 * 2^3 401.6 右移—— “除以2的幂”二进制位向右移动左侧补符号位。每右移1位 除以2向下取整实例13 2 3原数 0000 1101 (13) 右移2位0000 0011 (3) # 相当于 13 // 4 3二、位运算六大技巧从入门到高手技巧1判断奇偶性 ⚡O(1)# 传统方法ifx%21:# 奇数# 位运算优化直接判断第0位ifx1:# 奇数第0位为1原理二进制第0位为1则奇数为0则偶数。技巧2获取第 i 位# 获取x的二进制第i位从0开始bit(xi)1# 步骤拆解# 1. x i将第i位移到第0位# 2. 1提取第0位的值技巧3设置第 i 位为 1x|(1i)# 原理1 i 生成只有第i位为1的数# 或运算有1则1保证第i位变为1其他位不变技巧4设置第 i 位为 0x~(1i)# 原理# 1. 1 i生成第i位为1的数# 2. ~(1 i)取反第i位变0其他位变1# 3. 运算第i位强制变0其他位保持不变技巧5判断是否为2的幂 ⭐高频考点defis_power_of_two(x):returnx0and(x(x-1))0# 原理2的幂二进制只有1个1# 例如8 1000, 7 0111# 8 7 0000 0 ✓# 非2的幂6 0110, 5 0101# 6 5 0100 ≠ 0 ✗技巧6获取最低位的1Lowbit⭐树状数组核心deflowbit(x):returnx(-x)# 原理利用补码特性# 例如x 12 1100# -x -12 补码(0100)# 12 (-12) 0100 4# 结果提取出最低位的1及其后面的0三、每日一题实战演练 题目1二进制中1的个数题目链接蓝桥杯1331题目描述给定整数x xx输出其二进制表示中1的个数。输入32位整数x xx注意包含负数输出1的个数示例输入9 输出2 # 解释9 1001有2个1解法一逐位判断通用处理负数xint(input())ans0foriinrange(32):# 遍历32个二进制位if(xi)1:# 获取第i位ans1print(ans)复杂度时间O ( 32 ) O(32)O(32)空间O ( 1 ) O(1)O(1)解法二Lowbit优化仅非负数defcount_ones(x):ans0whilex:x-x(-x)# 每次消去最低位的1ans1returnans# 原理lowbit提取最低位的1减去它就消去了这个1# 循环次数 1的个数效率更高⚠️注意本题输入含负数负数在Python中右移会无限填充1因此必须使用32位遍历法 题目2区间或题目链接蓝桥杯3691题目描述给定数组a aaq qq次询问每次求区间[ l , r ] [l,r][l,r]的按位或结果。关键思路或运算性质只要有1就为1区间或 对每一位单独计算只要区间内该位至少有一个1结果该位就是1fromitertoolsimportaccumulateimportsysinputsys.stdin.readlineprintsys.stdout.write n,qmap(int,input().split())alist(map(int,input().split()))# 对每一位单独处理a_bit[]foriinrange(31):# 遍历31个二进制位now_bit[]forxina:now_bit.append((xi)1)# 提取每个数第i位# 前缀和快速计算区间该位是否有1a_bit.append(list(accumulate(now_bit)))for_inrange(q):l,rmap(int,input().split())l-1;r-1# 转0-indexedans0foriinrange(31):ifl0:nowa_bit[i][r]else:nowa_bit[i][r]-a_bit[i][l-1]ifnow0:# 该位区间内有1ans|(1i)# 设置结果该位为1print(str(ans)\n)复杂度预处理O ( 31 × n ) O(31 \times n)O(31×n)每次查询O ( 31 ) O(31)O(31) 题目3异或森林蓝桥杯3400⭐难题题目链接蓝桥杯3400题目描述求满足条件的子数组数量使得子数组所有元素异或结果的因数个数为偶数。核心转化区间异或 前缀异或a[l]^...^a[r] pre_xor[r] ^ pre_xor[l-1]因数个数为偶数 ⟺ 该数为非完全平方数完全平方数的因数个数为奇数如4的因数1,2,4非完全平方数的因数个数为偶数反向思考总子数组数 - 异或值为完全平方数的子数组数nint(input())alist(map(int,input().split()))# 前缀异或数组pre_xor[0]*n pre_xor[0]a[0]foriinrange(1,n):pre_xor[i]pre_xor[i-1]^a[i]ans0# 枚举所有可能的完全平方数a[i] n 10^4异或值范围有限forxinrange(0,200):xorx*x# 求异或值等于xor的区间个数# 即 pre_xor[i] ^ pre_xor[j] xor 的二元组i,j数目i j# 等价于pre_xor[i] pre_xor[j] ^ xordic{}dic[0]1# pre_xor[-1] 0处理从0开始的区间forjinrange(n):ansdic.get(pre_xor[j]^xor,0)dic[pre_xor[j]]dic.get(pre_xor[j],0)1# 总子数组数 - 异或值为完全平方数的子数组数totaln*(n1)//2print(total-ans)复杂度时间O ( 200 × n ) O(200 \times n)O(200×n)空间O ( n ) O(n)O(n)四、位运算常见应用场景总结应用场景位运算技巧时间复杂度判断奇偶x 1O ( 1 ) O(1)O(1)交换两数a ^ b; b ^ a; a ^ bO ( 1 ) O(1)O(1)判断2的幂x (x-1) 0O ( 1 ) O(1)O(1)消去最低位1x x - 1O ( 1 ) O(1)O(1)获取最低位1x (-x)O ( 1 ) O(1)O(1)状态压缩DP用二进制表示集合O ( 2 n × n ) O(2^n \times n)O(2n×n)树状数组lowbit操作O ( log ⁡ n ) O(\log n)O(logn)五、今日打卡练习练习1实现一个函数判断一个数的二进制表示是否为回文。练习2给定数组求所有子数组的异或和之和。练习3LeetCode 136. 只出现一次的数字 —— 异或经典题六、结语位运算的魅力在于用二进制的视角重新审视问题。当你熟练运用这些技巧后很多看似复杂的题目都会变得简洁优雅。学习建议熟记六大基础运算的真值表重点掌握异或的五大性质交换律、结合律、自反性等多练习按位独立考虑的思维方式关注lowbit操作它是树状数组和线段树的基础如果本文对你有帮助欢迎点赞 收藏 ⭐ 关注 你的支持是我持续更新的动力