位运算基础

概念讲解

常见位运算

运算符 名称 说明
& 按位与 都为 1 才为 1
| 按位或 有 1 就为 1
^ 按位异或 不同为 1
~ 按位取反 0 变 1，1 变 0
<< 左移 乘以 2^n
>> 右移 除以 2^n

常见应用

奇偶判断

12if (n & 1) { /* 奇数 */ }
else { /* 偶数 */ }

乘除 2 的幂

12n << 1  // n * 2
n >> 1  // n / 2

交换两个数

123a ^= b;
b ^= a;
a ^= b;

lowbit 操作

123int lowbit(int x) {
    return x & (-x);
}

考点分析

初赛考查方式

  1. 选择题： 位运算结果
  2. 程序阅读： 位运算程序
  3. 填空题： 位运算应用

常见考点

  • 位运算计算
  • 奇偶判断
  • lowbit 操作

例题精讲

例题 1：位运算

题目： 5 & 3 是多少？

解答：

5 = 101
3 = 011
--------
5 & 3 = 001 = 1

例题 2：lowbit

题目： lowbit(12) 是多少？

解答：

12 = 1100
-12 = 0100（补码）
12 & (-12) = 0100 = 4

练习题

  1. 5 | 3 是多少？
查看答案

7

5 = 101
3 = 011
--------
5 | 3 = 111 = 7
  1. 5 ^ 3 是多少？
查看答案

6

5 = 101
3 = 011
--------
5 ^ 3 = 110 = 6
  1. lowbit(6) 是多少？
查看答案

2

6 = 110
-6 = 010（补码）
6 & (-6) = 010 = 2

易错点

⚠️ 注意：

  1. 位运算优先级低，要加括号
  2. 左移可能溢出
  3. 负数用补码表示
  4. lowbit 在树状数组中很重要