第4章 位运算

🎯 本章学习目标

学完本章，你将能够：

1. 理解位运算的本质：直接对二进制位逐位操作
2. 熟练掌握 6 种位运算符的真值表和手算方法
3. 记住按位取反公式：~x = -x - 1
4. 掌握异或的四条性质（与0异或、自身异或、交换律、结合律）及自反性
5. 理解左移与乘 2、右移与除 2 的关系及适用条件
6. 明确负数算术右移（高位补符号位、向下取整）的特点
7. 牢记位运算的优先级陷阱：位运算符低于比较运算符
8. 区分位运算（& |）与逻辑运算（&& ||）的区别
9. 掌握位运算经典应用：判奇偶、交换变量、消最低位1、lowbit
10. 理解状态压缩的基本思想：用二进制位表示开关状态

---

🗺️ 本章知识图谱

位运算
├── 基本概念
│   ├── 操作对象：整数的二进制补码
│   └── 六种运算符
├── 按位与 &
│   ├── 规则：全1出1
│   ├── 用途：取指定位、掩码、判断奇偶 x&1
│   └── 配合 ~ 实现清位：x & ~(1<<k)
├── 按位或 |
│   ├── 规则：有1出1
│   └── 用途：把指定位置1、置标志位
├── 按位非 ~
│   ├── 规则：逐位取反（单目）
│   ├── 核心公式：~x = -x - 1
│   └── 特殊值：~0 = -1，~(-1) = 0
├── 按位异或 ^
│   ├── 规则：相同为0，相异为1
│   ├── 性质：a^0=a, a^a=0, 交换律, 结合律
│   ├── 自反性：a^b^b = a
│   └── 应用：交换变量、加密、翻转指定位
├── 左移 <<
│   ├── 规则：各位左移，低位补0
│   └── 效果：左移n位 = ×2ⁿ（不溢出时）
├── 右移 >>
│   ├── 算术右移：高位补符号位（有符号数）
│   ├── 逻辑右移：高位补0（无符号数）
│   └── 效果：右移n位 = ÷2ⁿ（负数向下取整）
├── 优先级与复合赋值
│   ├── 优先级：移位 > 比较 > & > ^ > | > 逻辑
│   ├── 陷阱：x&1==0 等价于 x&(1==0)，必须加括号
│   └── 复合赋值：&= |= ^= <<= >>=
└── 经典应用
    ├── 判断奇偶：x & 1
    ├── 交换变量：异或三连
    ├── 消最低位1：x & (x-1)
    ├── 取最低位1（lowbit）：x & -x
    ├── 判断2的幂：x>0 且 (x&(x-1))==0
    ├── 统计二进制中1的个数
    └── 状态压缩：用位表示开关状态

---

一、位运算基础

1.1 什么是位运算？

我们平时写的 +、-、*、/ 是对整个数进行运算；而位运算是把整数写成二进制后，对每一个二进制位（bit）逐位进行的运算。

位运算的操作数必须是整数（char、short、int、long long 等），运算结果也是整数。

GESP三级考纲要求掌握 6 种位运算符：

运算符	名称	运算规则（口诀）	典型用途
&	按位与	全1为1，有0为0	取指定位、掩码、判断奇偶
|	按位或	有1为1，全0为0	把指定位置1、合并标志
~	按位非	0变1，1变0（单目）	配合 & 实现清位
^	按位异或	相同为0，相异为1	交换变量、简单加密、翻转位
<<	左移	各位左移，低位补0	快速乘以 2 的幂
>>	右移	各位右移	快速除以 2 的幂

🔥 高频考点： 位运算的题目几乎都要求手算二进制。做题时第一步永远是：把参与运算的数写成二进制（位数对齐，不足补0），再逐位运算，最后转回十进制。

⚠️ 易错点： 位运算针对的是整数在内存中的补码形式。正数的补码是它本身；负数的补码是"按位取反再加1"。复习补码知识可以回看第 2 章《数据编码》。

1.2 手算的标准姿势

以两个 4 位二进制数为例，做位运算时把位数对齐：

   5 = 0101
   3 = 0011
   --------
 &     0001   （逐位"与"）
 |     0111   （逐位"或"）
 ^     0110   （逐位"异或"）

下面我们逐个运算符精讲，每个都配真值表 + 手算例题 + C++代码。

---

二、按位与 &

2.1 真值表

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

口诀：全1为1，有0为0。可以理解为"两位都同意，结果才通过"。

2.2 手算例题

计算 5 & 3：

   5 = 0101
   3 = 0011
   ---------
 &     0001 = 1

所以 5 & 3 = 1。

2.3 三大用途

用途1：取（保留）指定的二进制位 —— 掩码（Mask）

想保留哪些位，就让掩码 mask 的哪些位为1，其余为0：

   x    = 1101 0110   （想保留低4位）
   mask = 0000 1111   （0xF）
   ----------------
 &        0000 0110   （低4位被原样取出，高4位清零）

用途2：把指定的位清0（置0）

让掩码在想清零的位上为0即可（配合 ~ 更方便，见第四节）。

用途3：判断奇偶 x & 1

二进制最低位是1则为奇数，是0则为偶数。x & 1 取出最低位：结果为1是奇数，为0是偶数。

2.4 代码

#include <iostream>
using namespace std;

int main() {
    // 5 = 0101, 3 = 0011
    cout << (5 & 3) << endl;    // 输出 1：0101 & 0011 = 0001

    int x = 13;                 // 13 = 1101
    cout << (x & 1) << endl;    // 输出 1：最低位为1，13是奇数
    cout << (x & 0xF) << endl;  // 输出 13：掩码 0xF(1111) 取出低4位

    int y = 12;                 // 12 = 1100
    cout << (y & 1) << endl;    // 输出 0：最低位为0，12是偶数
    return 0;
}

🔥 高频考点： x & 1 判断奇偶是三级考试最高频的位运算用法，比 x % 2 更"贴近硬件"。注意：位运算 & 和逻辑与 && 是两个完全不同的运算符（详见第八节）。

---

三、按位或 |

3.1 真值表

a	b	a | b
0	0	0
0	1	1
1	0	1
1	1	1

口诀：有1为1，全0为0。可以理解为"只要有一位同意，结果就通过"。

3.2 手算例题

计算 5 | 3：

   5 = 0101
   3 = 0011
   ---------
 |     0111 = 7

所以 5 | 3 = 7。

3.3 主要用途：把指定的位置1

想让哪些位变成1，就让掩码的哪些位为1，再做按位或。原来是1的位保持1，原来是0的位被改成1。这在"开关标志位"中极其常用：

#include <iostream>
using namespace std;

int main() {
    int flags = 0;              // 0000：所有开关初始关闭
    flags |= (1 << 0);          // 第0位置1：0001，打开开关A
    flags |= (1 << 2);          // 第2位置1：0101，打开开关C
    cout << flags << endl;      // 输出 5（二进制 0101）

    cout << (5 | 3) << endl;    // 输出 7：0101 | 0011 = 0111
    return 0;
}

💡 小结记忆： & 用来"取位/清0"（掩码位为1才保留），| 用来"置1"（掩码位为1就置1）。一个管"关"，一个管"开"。

---

四、按位非 ~

4.1 真值表

~ 是单目运算符（只有一个操作数），把每一位都翻转：

a	~a
0	1
1	0

口诀：0变1，1变0。

4.2 核心公式：~x = -x - 1

这是本节最重要的结论 🔥。结合补码推导：

我们知道，在补码体系中，一个数的相反数 = 按位取反再加1：

-x = ~x + 1

把等式移项，立即得到：

~x = -x - 1

手算验证 ~5：

 5 的补码 = 0000 0101
~5        = 1111 1010   （每一位翻转）

1111 1010 是哪个数的补码？用公式 ~x = -x - 1：~5 = -5 - 1 = -6。

验证：-6 的补码 = ~6 + 1 = ~(0000 0110) + 1 = 1111 1001 + 1 = 1111 1010 ✓ 完全一致。

再记两个特殊值：

表达式	结果	说明
~0	-1	0 取反后全是1，全1补码表示 -1
~(-1)	0	-1 取反后全是0
~5	-6	-5-1
~(-6)	5	自反验证

⚠️ 易错点： ~ 的结果不是简单的"正数变负数"！~5 不等于 -5，而是 -6。考试常在选择题里用 -5 做干扰项，务必牢记公式 ~x = -x - 1。

4.3 代码

#include <iostream>
using namespace std;

int main() {
    int a = 5;
    cout << ~a << endl;        // 输出 -6：~x = -x - 1
    cout << ~0 << endl;        // 输出 -1

    unsigned int u = 0;        // 无符号数
    cout << ~u << endl;        // 输出 4294967295（32位全1，即 2^32 - 1）
    return 0;
}

💡 ~ 很少单独使用，它最常见的搭档是 &：把第 k 位清零写作 x & ~(1 << k)——~(1<<k) 会得到"除第k位外全是1"的掩码，与一下就只把第k位清0，其余位不变。

---

五、按位异或 ^

5.1 真值表

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

口诀：相同为0，相异为1。异或可以理解为"不带进位的二进制加法"。

5.2 手算例题

计算 5 ^ 3：

   5 = 0101
   3 = 0011
   ---------
 ^     0110 = 6

所以 5 ^ 3 = 6。

5.3 四条必记性质 🔥

性质	公式	说明
与0异或	a ^ 0 = a	0不改变任何位
自身异或	a ^ a = 0	相同位全变0
交换律	a ^ b = b ^ a	—
结合律	(a ^ b) ^ c = a ^ (b ^ c)	—

由上面性质推出自反性（异或最重要的性质）：

a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a

即：一个数异或同一个数两次，会恢复原样。交换变量和加密都靠它！

5.4 应用1：不用临时变量交换两个数

#include <iostream>
using namespace std;

int main() {
    int a = 12, b = 7;
    a ^= b;   // a = 12 ^ 7 = 11  (1100 ^ 0111 = 1011)
    b ^= a;   // b = 7 ^ 11 = 12  (0111 ^ 1011 = 1100)
    a ^= b;   // a = 11 ^ 12 = 7  (1011 ^ 1100 = 0111)
    cout << a << " " << b << endl;   // 输出 7 12，交换完成！
    return 0;
}

原理（利用自反性）：

第1步：a' = a ^ b
第2步：b' = b ^ a' = b ^ (a ^ b) = a ^ (b ^ b) = a ^ 0 = a   ← b 变成了原来的 a
第3步：a'' = a' ^ b' = (a ^ b) ^ a = b ^ (a ^ a) = b ^ 0 = b  ← a 变成了原来的 b

⚠️ 易错点： 异或交换时，千万不能对同一个变量（或同一地址）使用！例如 swap(a[i], a[i]) 时若 i 相同，a ^= a 会把变量变成0。考试中若考程序填空，要留意这个边界。

5.5 应用2：简单加密

利用自反性：明文 异或 密钥得到密文，密文再 异或 同一密钥就还原明文：

#include <iostream>
using namespace std;

int main() {
    int plain  = 2025;     // 明文
    int key    = 123;      // 密钥：密钥应为一个非零的整数，如果密钥为 0，加密无效
    int cipher = plain ^ key;   // 加密
    int back   = cipher ^ key;  // 解密：cipher ^ key = plain ^ key ^ key = plain
    cout << cipher << endl;     // 密文（一个看似无规律的数）
    cout << back << endl;       // 输出 2025，还原成功
    return 0;
}

💡 异或还可以翻转指定的位：x ^ (1 << k) 会把第 k 位翻转（0变1、1变0），其余位不变。

---

六、左移 <<

6.1 运算规则

把各二进制位全部向左移动 n 位，左边移出的位丢弃，右边低位补0。

   3 = 0011
   3 << 2 = 1100 = 12

6.2 核心结论：左移 n 位 = 乘以 2ⁿ 🔥

低位补0，相当于在二进制末尾添0，每添一个0数值就翻倍：

表达式	二进制变化	结果	等价于
5 << 1	0101 → 1010	10	5 × 2
3 << 2	0011 → 1100	12	3 × 4
1 << 4	0001 → 10000	16	1 × 2⁴

#include <iostream>
using namespace std;

int main() {
    cout << (5 << 1) << endl;   // 输出 10，相当于 5 * 2
    cout << (3 << 2) << endl;   // 输出 12，相当于 3 * 4
    cout << (1 << 4) << endl;   // 输出 16，构造"第4位为1"的掩码常用写法
    return 0;
}

⚠️ 易错点： C++ 中整数位数固定（int 为32位），左移把"1"移进符号位或超出位宽会导致溢出/未定义行为；移位位数若 ≥ 数据位宽（如 int 移32位）也是未定义行为。

---

七、右移 >>

7.1 运算规则与两种右移

把各二进制位全部向右移动 n 位，右边移出的位丢弃，左边高位补什么是关键：

类型	高位补什么	适用对象
逻辑右移	补 0	无符号数（unsigned）
算术右移	补符号位（正数补0，负数补1）	有符号数（绝大多数编译器如此实现）

算术右移高位补符号位，是为了保证负数右移后仍然是负数、且符合"除以2"的数学含义。

7.2 核心结论：右移 n 位 = 除以 2ⁿ 取整 🔥

  12 = 1100
  12 >> 2 = 0011 = 3        （12 / 4 = 3）

  -8 = ...1111 1000
  -8 >> 1 = ...1111 1100 = -4   （-8 / 2 = -4，算术右移高位补1）

表达式	结果	说明
12 >> 2	3	12 ÷ 4
7 >> 1	3	7 ÷ 2 取整（向0取整）
-8 >> 1	-4	-8 ÷ 2
-7 >> 1	-4	-7 ÷ 2，算术右移向下取整得 -4（不是 -3！）

#include <iostream>
using namespace std;

int main() {
    cout << (12 >> 2) << endl;   // 输出 3，相当于 12 / 4
    cout << (7 >> 1) << endl;    // 输出 3，相当于 7 / 2 取整
    cout << (-8 >> 1) << endl;   // 输出 -4，有符号数算术右移，高位补1

    unsigned int u = 0xF0;       // 1111 0000
    cout << (u >> 4) << endl;    // 输出 15：无符号数逻辑右移，高位补0 → 0000 1111
    return 0;
}

⚠️ 易错点： 负数右移是向下取整（floor），不是"去掉小数部分"。-7 >> 1 = -4 而不是 -3。考试若考负数移位，这是最容易丢分的地方。

💡 移位小窍门： 1 << k 用来快速构造"第 k 位为1"的掩码；x >> k & 1 用来取出 x 的第 k 位。这两个写法在状态压缩中随处可见。

---

八、位运算的优先级与复合赋值

8.1 优先级表

从高到低排列（只列相关运算符）：

优先级（高→低）	运算符	类别
1	<< >>	移位
2	< <= > >=	关系运算
3	== !=	相等判断
4	&	按位与
5	^	按位异或
6	|	按位或
7	&&	逻辑与
8	||	逻辑或
补充：~（按位非）：~ 的优先级与 +、-（正负号）同级，属于一元运算符，优先级非常高（高于移位运算）

🔥🔥 最高频陷阱：位运算符的优先级低于比较运算符！

因此 x & 1 == 0 并不会按 (x & 1) == 0 计算，而是被解析成： x & (1 == 0) // 1 == 0 结果为 0（假），于是变成 x & 0，永远为 0（假）！

位运算表达式里，只要混合了比较运算，一定要加括号！ 正确写法：if ((x & 1) == 0)。

8.2 位运算 & | 与逻辑运算 && || 的区别

对比项	& |（位运算）	&& ||（逻辑运算）
操作	逐位运算，结果是整数	判断真假，结果只能是 0 或 1
短路	不短路，两边都算	短路求值（&& 左假则右不算，|| 左真则右不算）
例子	2 & 4 = 10 & 100 = 0	2 && 4 = 1（两个都非零，为真）

#include <iostream>
using namespace std;

int main() {
    int a = 2, b = 4;       // a = 10, b = 100
    cout << (a & b) << endl;   // 输出 0：二进制没有共同的1
    cout << (a && b) << endl;  // 输出 1：两个数都非零，逻辑为真

    int x = 6;
    if (x & 1 == 0)            // 陷阱！等价于 x & (1 == 0) = x & 0 = 0，恒为假
        cout << "even";
    else
        cout << "odd";         // 实际输出 odd（虽然 6 明明是偶数！）
    cout << endl;

    if ((x & 1) == 0)          // 正确写法：加括号
        cout << "even" << endl; // 输出 even
    return 0;
}

8.3 复合位赋值运算符

和 +=、-= 类似，位运算也有复合赋值：

复合运算符	等价于	常见用途
a &= b	a = a & b	清位
a |= b	a = a | b	置1
a ^= b	a = a ^ b	翻转/交换/加密
a <<= n	a = a << n	左移后存回
a >>= n	a = a >> n	右移后存回

---

九、经典应用三连

9.1 判断一个数是不是 2 的幂

原理： 2 的幂的二进制形式有且仅有一个1（如 8 = 1000，16 = 10000）。而 x & (x - 1) 的作用是把最低位的1消掉：

   8 = 1000
   7 = 0111
   ---------
 &     0000 = 0      ← 唯一的1被消掉，结果为0 → 是2的幂

  12 = 1100
  11 = 1011
   ---------
 &     1000 = 8 ≠ 0  ← 还剩一个1 → 不是2的幂

结论：x > 0 且 (x & (x - 1)) == 0，则 x 是 2 的幂（别忘记 x>0，因为 0 也满足等于0，但 0 不是2的幂）。

9.2 统计二进制中 1 的个数

反复执行 x &= x - 1，每执行一次消掉一个1，执行次数就是1的个数：

#include <iostream>
using namespace std;

// 判断2的幂
bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

// 统计二进制中1的个数（ Brian Kernighan 算法思想）
int countOnes(int x) {
    int cnt = 0;
    while (x != 0) {
        x &= x - 1;   // 消掉最低位的1
        cnt++;
    }
    return cnt;
}

// lowbit：适用于 x > 0 的正整数，取出最低位的 1 所对应的值
int lowbit(int x) {
    return x & -x;    // 如 12(1100) & -12(...0100) = 4(0100)
}

int main() {
    cout << isPowerOfTwo(8) << endl;   // 1（真）
    cout << isPowerOfTwo(12) << endl;  // 0（假）
    cout << countOnes(13) << endl;     // 3：13 = 1101 有三个1
    cout << lowbit(12) << endl;        // 4：最低位的1在第2位，值为 2^2 = 4
    return 0;
}

🔥 高频考点： x & (x-1)（消最低位1）和 x & -x（取最低位1，即 lowbit）是程序阅读题的"明星代码"。看到这两个式子要条件反射般认出它们的作用。lowbit 思想在后续学习树状数组时还会大放异彩。

9.3 状态压缩思想入门

当一个问题只有"开/关""是/否"两种状态时，可以用一个二进制位表示一个状态，一个整数就能装下几十个开关——这就是状态压缩：

#include <iostream>
using namespace std;

int main() {
    int state = 0;              // 000：3盏灯全关
    state |= (1 << 0);          // 开第0盏灯 → 001
    state |= (1 << 2);          // 开第2盏灯 → 101

    if (state & (1 << 1))       // 检查第1盏灯是否开着（101 & 010 = 0，关着）
        cout << "灯1亮着" << endl;

    state &= ~(1 << 0);         // 关掉第0盏灯 → 100
    cout << state << endl;      // 输出 4（二进制 100）
    return 0;
}

三级阶段只需理解"用位表示状态"的思想即可，更复杂的状态压缩动态规划是后面的内容。

---

十、📝 实战练习

以下题目均改编自 GESP 三级历年真题考点，重点考查表达式结果判断与程序阅读。建议先自己动手写出二进制过程，再看解析。 想刷更多同类型题，推荐到 百练百会（官网：www.bestwit.cn），或在微信小程序搜索"百练百会"）按知识点专项练习，即时判分、逐题精讲。

练习题 1（单选题）

题目： 表达式 10 & 12 | 3 的值是（ ）

A. 10　　B. 11　　C. 8　　D. 15

🔑 点击查看答案与解析

答案： B

解析： 位运算符中 & 优先级高于 |（三者的优先级为 & > ^ > |），先算 10 & 12：

  10 = 1010
  12 = 1100
  ----------
 &     1000 = 8

再算 8 | 3：

   8 = 1000
   3 = 0011
   ---------
 |     1011 = 11

结果为 11，选 B。

注意：若错误地先算 12 | 3 = 1111 = 15，再算 10 & 15 = 1010 = 10，会误选 A——这正是优先级设下的陷阱。

---

练习题 2（单选题）

题目： 在 C++ 中，int a = 5; 则表达式 ~a 的值是（ ）

A. 5　　B. -5　　C. -6　　D. 250

🔑 点击查看答案与解析

答案： C

解析： 由补码公式 ~x = -x - 1，得 ~5 = -5 - 1 = -6。

手算验证：

  5 的补码 = 0000 0101
 ~5        = 1111 1010

1111 1010 是 -6 的补码（-6 = ~6 + 1 = 1111 1001 + 1 = 1111 1010）✓。

选 C。选项 B（-5）是"取反就是变负"的典型错误理解。

---

练习题 3（程序阅读题）

题目： 阅读以下 C++ 程序，输出结果是（ ）

int a = 12, b = 7;
a ^= b;
b ^= a;
a ^= b;
cout << a << " " << b;

A. 12 7　　B. 7 12　　C. 11 12　　D. 7 7

🔑 点击查看答案与解析

答案： B

解析： 这是经典的异或交换，逐步追踪：

初始：  a = 12 (1100), b = 7 (0111)
a ^= b：a = 1100 ^ 0111 = 1011 = 11
b ^= a：b = 0111 ^ 1011 = 1100 = 12
a ^= b：a = 1011 ^ 1100 = 0111 = 7

最终 a = 7，b = 12，两数在没有使用临时变量的情况下完成交换，输出 7 12，选 B。

---

练习题 4（程序阅读题）

题目： 阅读以下 C++ 程序，输出结果是（ ）

#include <iostream>
using namespace std;
int main() {
    int x = 6;
    if (x & 1 == 0)
        cout << "even";
    else
        cout << "odd";
    return 0;
}

A. even　　B. odd　　C. 编译错误　　D. 无输出

🔑 点击查看答案与解析

答案： B

解析： 本题考查位运算优先级。== 的优先级高于 &，所以条件实际被解析为：

x & (1 == 0)   // 1 == 0 结果为 0（假）
= x & 0        // 任何数 & 0 都为 0（假）

条件恒为假，程序走 else 分支，输出 odd——尽管 6 明明是偶数！选 B。

正确写法应给位运算加括号：if ((x & 1) == 0)，此时才会输出 even。

---

练习题 5（程序阅读题）

题目： 阅读以下 C++ 程序，输出结果是（ ）

int x = 13, cnt = 0;
while (x) {
    x &= x - 1;
    cnt++;
}
cout << cnt;

A. 1　　B. 2　　C. 3　　D. 4

🔑 点击查看答案与解析

答案： C

解析： x &= x - 1 的作用是消掉 x 二进制中最低位的1，循环次数就是1的个数。13 = 1101，追踪如下：

第1轮：x = 13 (1101)，x & 12 = 1101 & 1100 = 1100 = 12，cnt = 1
第2轮：x = 12 (1100)，x & 11 = 1100 & 1011 = 1000 = 8， cnt = 2
第3轮：x = 8  (1000)，x & 7  = 1000 & 0111 = 0000 = 0， cnt = 3
x 变为 0，循环结束

输出 3，选 C。13 的二进制 1101 中恰好有三个1，程序的功能正是统计二进制中1的个数。

---

练习题 6（单选题）

题目： 表达式 24 >> 2 的值是（ ），表达式 -7 >> 1 的值是（ ）

A. 6, -3　　B. 6, -4　　C. 12, -3　　D. 12, -4

🔑 点击查看答案与解析

答案： B

解析：

• 24 >> 2：24 的二进制是 11000，右移 2 位得 110 = 6。等价于 24 ÷ 4 = 6 ✅
• -7 >> 1：负数右移是算术右移（高位补符号位 1），结果向下取整。-7 ÷ 2 = -3.5，向下取整得 -4（不是 -3！）。

验证：

-7 的补码（8位）：1111 1001
右移1位（算术右移，高位补1）：1111 1100
1111 1100 是哪个数的补码？数值位再求补：000 0100 → 4 → -4 ✓

选 B（6, -4）。

🔥 高频易错点：负数右移是向下取整（向负无穷方向取整），不是"去掉小数部分"。-7 >> 1 = -4 而不是 -3，这是考试经典坑。

---

练习题 7（判断题）

题目： 判断下列说法是否正确，正确打"√"，错误打"×"。

(1) 按位异或满足交换律和结合律。（ ） (2) x | 0 的结果等于 0。（ ） (3) 左移一位一定等价于乘以 2。（ ） (4) a ^ b ^ b 的结果等于 a。（ ） (5) 位运算的操作数可以是浮点数。（ ） (6) x & (x - 1) 的作用是把 x 二进制中最低位的 1 变成 0。（ ）

🔑 点击查看答案与解析

答案： (1) √　(2) ×　(3) ×　(4) √　(5) ×　(6) √

解析：

• (1) √：异或满足交换律（a^b = b^a）和结合律（(a^b)^c = a^(b^c)）。
• (2) ×：x | 0 的结果等于 x 本身（有1出1，全0才出0，和0或不改变任何位）。等于 0 的是 x & 0。
• (3) ×：在不溢出的前提下左移一位等价于乘 2。如果高位的 1 被移出（溢出），结果就不等价了。
• (4) √：异或自反性——一个数异或同一个数两次恢复原样。
• (5) ×：位运算只能用于整数类型（char、short、int、long long 等），不能用于浮点数。
• (6) √：这是 Brian Kernighan 算法的核心操作，每执行一次消掉一个 1。

---

练习题 8（编程题）

题目： 输入一个正整数 n，输出 n 的二进制表示中 1 的个数。

输入样例：

13

输出样例：

3

（解释：13 = 1101，有 3 个 1）

🔑 点击查看答案与解析

C++ 参考代码（方法一：Brian Kernighan 算法，推荐）：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    while (n != 0) {
        n = n & (n - 1);   // 消掉最低位的 1
        cnt++;
    }

    cout << cnt << endl;
    return 0;
}

C++ 参考代码（方法二：逐位检查法，更直观）：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 0; i < 32; i++) {   // int 共32位，逐位检查
        if ((n >> i) & 1) {          // 第 i 位是 1 吗？
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

解析：

• 方法一（Brian Kernighan 算法）：每次执行 n &= n-1 就消掉最低位的一个 1，循环次数等于 1 的个数。时间复杂度 O(k)，k 是 1 的个数，比逐位检查更快。
• 方法二（逐位检查）：从第 0 位到第 31 位，依次右移后和 1 按位与，判断该位是否为 1。思路简单直接，适合初学者。

验证：13 = 1101，有 3 个 1 ✓

🔥 考点延伸：lowbit(x) = x & -x 可以取出最低位的 1 对应的值（如 lowbit(12) = 4）。lowbit 是树状数组等高级数据结构的基础，三级阶段了解即可。

---

十一、📊 考点总结表

考点	重要程度	出题形式	易错点
六种位运算符真值表与手算	⭐⭐⭐⭐	选择/表达式求值	位数没对齐；按位或和按位与搞反
& 判奇偶 x & 1、掩码取位	⭐⭐⭐⭐	选择/程序阅读	忘了 & 要加括号
~x = -x - 1（结合补码）	⭐⭐⭐⭐	选择/判断	误以为 ~5 = -5（实际是 -6）
异或自反性、异或交换、加密	⭐⭐⭐⭐	程序阅读/填空	交换变量时 a 和 a 交换变成 0
左移 = ×2ⁿ、右移 = ÷2ⁿ	⭐⭐⭐⭐	选择/计算	忽略溢出条件；负数右移记错
负数算术右移（向下取整）	⭐⭐⭐⭐	选择/判断	以为 -7>>1 = -3（实际是 -4）
位运算优先级陷阱（x & 1 == 0）	⭐⭐⭐⭐⭐	程序阅读/判断	忘记加括号；以为 & 比 == 优先级高
& | 与 && || 的区别	⭐⭐⭐⭐	选择/判断	混淆位运算和逻辑运算；短路求值差异
复合位赋值 &= |= ^= <<= >>=	⭐⭐⭐	程序填空	复合运算符写法记错
2的幂、统计1的个数、lowbit	⭐⭐⭐⭐	程序阅读/填空	判断2的幂忘了 x>0 的条件
状态压缩思想	⭐⭐⭐	了解/入门	不理解"用位表示状态"的思想

---

⭐ 必背速记卡

┌──────────────────────────────────────────────────────┐
│              ⭐ 位运算必背速记卡                         │
├──────────────────────────────────────────────────────┤
│  1. 按位与&：全1出1；按位或|：有1出1；异或^：相异出1   │
│  2. 按位取反公式：~x = -x - 1（~5 = -6）              │
│  3. ~0 = -1（全1）；~(-1) = 0（全0）                  │
│  4. 异或四性质：a^0=a, a^a=0, 交换律, 结合律          │
│  5. 异或自反性：a ^ b ^ b = a（异或两次还原）          │
│  6. 左移n位 = ×2ⁿ；右移n位 = ÷2ⁿ（不溢出时）          │
│  7. 负数算术右移高位补1，向下取整（-7>>1=-4不是-3）    │
│  8. 位运算优先级 < 比较运算，x&1==0 必须写成 (x&1)==0 │
│  9. 位运算不短路，逻辑运算短路；&|结果是整数，&&||是0/1│
│ 10. 判断奇偶：x & 1（比 x%2 更高效）                  │
│ 11. 消最低位1：x & (x-1)；取最低位1（lowbit）：x & -x  │
│ 12. 2的幂判断：x > 0 且 (x & (x-1)) == 0              │
│ 13. 状态压缩：1<<k 构造第k位掩码，&检查，|置1         │
└──────────────────────────────────────────────────────┘

---