位运算是指在二进制位的层面上直接对整数进行操作的运算。
- 数据在计算机中以二进制（0/1）存储
- 位运算比算术运算（+、-、*、/）快得多
- 常用于：权限控制、状态压缩、加密、图形处理、底层优化
1. 位运算符概念
C++ 中的 6 个基本位运算符：
| 运算符 | 名称 | 英文 | 说明 |
|---|---|---|---|
& | 按位与 | AND | 两位都为1 → 结果为1 |
| | 按位或 | OR | 至少一位为1 → 结果为1 |
^ | 按位异或 | XOR | 两位不同 → 结果为1 |
~ | 按位取反 | NOT | 0变1，1变0 |
<< | 左移 | SHL | 所有位向左移动，右侧补0 |
>> | 右移 | SHR | 所有位向右移动，左侧补符号位 |
注意：位运算符只能用于
int、long、short、char等整数类型
2. 位与（&）
规则表
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
常见用途
- 判断奇偶：
if (x & 1)→ 奇数 - 取特定位：
x & (1 << k)→ 判断第k位是否为1
3. 位或（|）
规则表
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
常见用途
- 设置特定位为1：
x | (1 << k) - 权限合并：
READ | WRITE | EXECUTE
4. 位异或（^）
规则表
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
重要性质
a ^ a = 0（自己异或自己得0）a ^ 0 = a（与0异或不变）a ^ b ^ b = a（两次异或还原）
常见用途
- 翻转特定位：
x ^ (1 << k) - 交换两数（不用临时变量）
- 找出出现奇数次的数
5. 位非（~）
规则
- 0 变 1
- 1 变 0
- 包括符号位也会取反
重要公式
~x = -x - 1
常见用途
- 清除特定位：
x & ~(1 << k) - 获取全1掩码：
~0
6. 左移（<<）
规则
- 所有位向左移动
- 右侧补 0
- 左侧超出的位被丢弃
数学意义
a << n = a × 2ⁿ
常见用途
- 快速乘以2的幂
- 构造掩码：
(1 << k)表示第k位为1
7. 右移（>>）
规则
- 所有位向右移动
- 左侧补符号位（正数补0，负数补1）
- 右侧超出的位被丢弃
数学意义
a >> n = ⌊a / 2ⁿ⌋ （向负无穷取整）
常见用途
- 快速除以2的幂
- 取高位数据
- 树状数组中的 lowbit 操作
8. 所有运算符速查表
| 运算 | 示例 | 结果 | 说明 |
|---|---|---|---|
| 与 | 5 & 3 | 1 | 0101 & 0011 = 0001 |
| 或 | 5 | 3 | 7 | 0101 | 0011 = 0111 |
| 异或 | 5 ^ 3 | 6 | 0101 ^ 0011 = 0110 |
| 取反 | ~5 | -6 | ~x = -x-1 |
| 左移 | 5 << 1 | 10 | ×2 |
| 右移 | 20 >> 1 | 10 | ÷2 |
9. 优先级提醒（重要！）
位运算符优先级低于判等运算符
// 错误
if (x & 1 == 0) // 实际是 x & (1==0) → x & 0
// 正确
if ((x & 1) == 0)
口诀：位运算一律加括号，安全第一不出错。