【每日一题】位运算

📌 写在前面：位运算是算法竞赛中的"隐形加速器"，它不仅能将O ( n ) O(n)O(n)优化到O ( 1 ) O(1)O(1)，更是状态压缩、树状数组等高级算法的基石。本文基于蓝桥杯官方课程，从二进制底层原理到竞赛实战，带你彻底掌握位运算！

一、位运算基础：二进制世界的六大法则

位运算直接对二进制位进行操作，是CPU最底层的运算方式，速度极快。

1.1 与运算&—— “有0则0，全1为1”

实例：6 & 11 = 2

0110 (6) & 1011 (11) -------- 0010 (2)

1.2 或运算|—— “有1则1，全0为0”

实例：6 | 11 = 15

0110 (6) | 1011 (11) -------- 1111 (15)

1.3 异或运算^—— “相同为0，不同为1” ⭐重点

核心性质（竞赛必考）：

• 交换律：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 = 13

0110 (6) ^ 1011 (11) -------- 1101 (13)

1.4 取反~—— “1变0，0变1”

实例：~6 = -7（在32位系统中，注意符号位）

~ 0000 0110 (6) -------- 1111 1001 (-7, 补码表示)

💡注意：Python中整数无限精度，~x = -x-1

1.5 左移<<—— “乘以2的幂”

二进制位向左移动，右侧补0。每左移1位 = 乘以2

实例：5 << 3 = 40

原数： 0000 0101 (5) 左移3位：0010 1000 (40) # 相当于 5 * 2^3 = 40

1.6 右移>>—— “除以2的幂”

二进制位向右移动，左侧补符号位。每右移1位 = 除以2（向下取整）

实例：13 >> 2 = 3

原数： 0000 1101 (13) 右移2位：0000 0011 (3) # 相当于 13 // 4 = 3

二、位运算六大技巧：从入门到高手

技巧1：判断奇偶性 ⚡O(1)

# 传统方法ifx%2==1:# 奇数# 位运算优化：直接判断第0位ifx&1:# 奇数（第0位为1）

原理：二进制第0位为1则奇数，为0则偶数。

技巧2：获取第 i 位

# 获取x的二进制第i位（从0开始）bit=(x>>i)&1# 步骤拆解：# 1. x >> i：将第i位移到第0位# 2. & 1：提取第0位的值

技巧3：设置第 i 位为 1

x|=(1<<i)# 原理：1 << i 生成只有第i位为1的数# 或运算：有1则1，保证第i位变为1，其他位不变

技巧4：设置第 i 位为 0

x&=~(1<<i)# 原理：# 1. 1 << i：生成第i位为1的数# 2. ~(1 << i)：取反，第i位变0，其他位变1# 3. &运算：第i位强制变0，其他位保持不变

技巧5：判断是否为2的幂 ⭐高频考点

defis_power_of_two(x):returnx>0and(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：获取最低位的1（Lowbit）⭐树状数组核心

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

解法一：逐位判断（通用，处理负数）

x=int(input())ans=0foriinrange(32):# 遍历32个二进制位if(x>>i)&1:# 获取第i位ans+=1print(ans)

复杂度：时间O ( 32 ) O(32)O(32)，空间O ( 1 ) O(1)O(1)

解法二：Lowbit优化（仅非负数）

defcount_ones(x):ans=0whilex:x-=x&(-x)# 每次消去最低位的1ans+=1returnans# 原理：lowbit提取最低位的1，减去它就消去了这个1# 循环次数 = 1的个数，效率更高

⚠️注意：本题输入含负数，负数在Python中右移会无限填充1，因此必须使用32位遍历法！

📝 题目2：区间或

题目链接：蓝桥杯3691

题目描述：给定数组a aa，q qq次询问，每次求区间[ l , r ] [l,r][l,r]的按位或结果。

关键思路：

• 或运算性质：只要有1就为1
• 区间或 = 对每一位单独计算，只要区间内该位至少有一个1，结果该位就是1

fromitertoolsimportaccumulateimportsysinput=sys.stdin.readlineprint=sys.stdout.write n,q=map(int,input().split())a=list(map(int,input().split()))# 对每一位单独处理a_bit=[]foriinrange(31):# 遍历31个二进制位now_bit=[]forxina:now_bit.append((x>>i)&1)# 提取每个数第i位# 前缀和：快速计算区间该位是否有1a_bit.append(list(accumulate(now_bit)))for_inrange(q):l,r=map(int,input().split())l-=1;r-=1# 转0-indexedans=0foriinrange(31):ifl==0:now=a_bit[i][r]else:now=a_bit[i][r]-a_bit[i][l-1]ifnow>0:# 该位区间内有1ans|=(1<<i)# 设置结果该位为1print(str(ans)+'\n')

复杂度：预处理O ( 31 × n ) O(31 \times n)O(31×n)，每次查询O ( 31 ) O(31)O(31)

📝 题目3：异或森林（蓝桥杯3400）⭐难题

题目链接：蓝桥杯3400

题目描述：求满足条件的子数组数量，使得子数组所有元素异或结果的因数个数为偶数。

核心转化

1. 区间异或 = 前缀异或：a[l]^...^a[r] = pre_xor[r] ^ pre_xor[l-1]
2. 因数个数为偶数 ⟺ 该数为非完全平方数
   • 完全平方数的因数个数为奇数（如4的因数：1,2,4）
   • 非完全平方数的因数个数为偶数
3. 反向思考：总子数组数 - 异或值为完全平方数的子数组数

n=int(input())a=list(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]ans=0# 枚举所有可能的完全平方数（a[i] <= n <= 10^4，异或值范围有限）forxinrange(0,200):xor=x*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):ans+=dic.get(pre_xor[j]^xor,0)dic[pre_xor[j]]=dic.get(pre_xor[j],0)+1# 总子数组数 - 异或值为完全平方数的子数组数total=n*(n+1)//2print(total-ans)

复杂度：时间O ( 200 × n ) O(200 \times n)O(200×n)，空间O ( n ) O(n)O(n)

四、位运算常见应用场景总结

五、今日打卡练习

📌练习1：实现一个函数，判断一个数的二进制表示是否为回文。

📌练习2：给定数组，求所有子数组的异或和之和。

📌练习3：LeetCode 136. 只出现一次的数字 —— 异或经典题

六、结语

位运算的魅力在于用二进制的视角重新审视问题。当你熟练运用这些技巧后，很多看似复杂的题目都会变得简洁优雅。

🌟学习建议：

1. 熟记六大基础运算的真值表
2. 重点掌握异或的五大性质（交换律、结合律、自反性等）
3. 多练习"按位独立考虑"的思维方式
4. 关注lowbit操作，它是树状数组和线段树的基础

如果本文对你有帮助，欢迎点赞 👍 + 收藏 ⭐ + 关注 🔔，你的支持是我持续更新的动力！