---
title: "03-位运算应用：与、或、异或、取反、左移"
aliases:
  - 位运算应用
created: 2026-08-29
tags:
  - 基础与理论
  - 信息的表示与处理
---
# 位运算应用：与、或、异或、取反、左移

> 本篇把原来五篇运算符笔记（与-掩码与清位 ／ 或-置位与合并 ／ 异或-翻转交换与加密 ／ 取反-负数与加法技巧 ／ 左移-乘2与生成掩码）合并为一篇，按"规则 → 性质 → 套路 → 例题"的统一节奏过一遍。技巧速查表在总篇 [[00-信息的表示与处理]] 6.4 节。

## 一、总览：六个运算符一张表

C 语言支持按位进行布尔运算，六件兵器各有各的脾气：

| 运算 | 读法 | 一句话口诀 | 类型 |
| --- | --- | --- | --- |
| `&` 与 | 同 1 为 1，有 0 则 0 | 想留下谁，就和 1 相与 | 双目 |
| `\|` 或 | 同 0 为 0，有 1 则 1 | 想打开谁，就和 1 相或 | 双目 |
| `^` 异或 | 相同为 0，不同为 1 | 想翻转谁，就和 1 异或 | 双目 |
| `~` 取反 | 0 变 1，1 变 0 | 连前导零一起翻 | 单目 |
| `<<` 左移 | 尾部补 0 | 相当于乘 2^k | 双目 |
| `>>` 右移 | 无符号补 0，有符号补符号位 | 相当于除 2^k（见总篇 6.2） | 双目 |

先把三篇里反复出现的同一组例子合并成一段代码，一次看全双目运算的效果：

```
#include <stdio.h>
int main() {
    int a = 0b1010;            // (1)
    int b = 0b0110;            // (2)
    printf("%d\n", (a & b));   // 2  ← 0010
    printf("%d\n", (a | b));   // 14 ← 1110
    printf("%d\n", (a ^ b));   // 12 ← 1100
    return 0;
}
```

(1) C 语言中以 0b 作为前缀表示二进制数，a 的实际值就是 (1010)；(2) 同理 b 是 (0110)；(3) 三个 printf 就是对 (1010) 和 (0110) 的每一位分别做 &、|、^ 运算。

注意：**前导零可有可无**，写上前导零只是为了对齐、让读者看清位运算的过程。

## 二、与 &：掩码与清位

### 2.1 规则与性质

位与运算对操作数的每一位按下表进行，每一位只有 0 或 1 两种情况，组合出来总共 4 种：

| x | y | x & y |
| --- | --- | --- |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |

得出两条结论：

1. 无论是 0 或 1，只要位与上 **1，还是它本身**
2. 无论是 0 或 1，只要位与上 **0，就变成 0**

所以对位与来说，**只要这一位上有一个 0，这一位的结果就会变成 0**——这就是"清位"的来源。

### 2.2 套路

**套路一：让某一位或某些位为 0**

x & 0xFE：

![[image-46e07ea0.png]]

0xFE 的最后一位是 0，所以不管 x 的最后一位是什么，结果都是 0；0xFE 的前 7 位都是 1，所以结果的前 7 位与 x 有关——**x 的前 7 位是什么，结果的前 7 位就是什么**。

**套路二：取一个数当中的一段**

x & 0xFF：

![[image-5851d92d.png]]

一个 int 有 32 比特 4 字节，对 0xFF 取 &，前面 3 个字节都会变成 0，最后一个字节是什么结果就保留什么。

> 💡 **一句话心法**：如果拿一个 1 去和另一个数相 &，就意味着"我们要看那个数是多少"；拿 0 去相 &，就是"这一位我不要了"。给出多少个二进制的 1，那些 1 对应的位就留下来，其他东西都被拿走了——这块"筛子"就叫**掩码（mask）**。

### 2.3 例题

#### 1、奇偶性判定

判断奇偶通常用取模 %：

```
#include <stdio.h>
int main() {
    if(5 % 2 == 1) { printf("5是奇数\n"); }
    if(6 % 2 == 0) { printf("6是偶数\n"); }
    return 0;
}
```

然而也可以这么写：

```
#include <stdio.h>
int main() {
    if(5 & 1) { printf("5是奇数\n"); }
    if( (6 & 1) == 0 ) { printf("6是偶数\n"); }
    return 0;
}
```

利用的是奇数和偶数二进制的特性：

![[2-Learning/01-基础与理论/02-信息的表示与处理/assets/image-2c0792ab.png]]

偶数的二进制末位必为 0，奇数必为 1。所以任何一个数和 0b1 位与，结果为零则末位为 0，是偶数；否则是奇数。

#### 2、取末 K 位

> 【例题1】给定一个数，求它的二进制表示的末五位，以十进制输出。

核心就是：只要末五位，剩下的位都不需要——位与上 0b11111 即可：

```
#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0b11111) );
    return 0;
}
```

> 【例题2】如果想得到末七位、末九位、末十四位、末 K 位呢？

```
#include <stdio.h>
int main() {
    int x, k;
    scanf("%d %d", &x, &k);
    int mask = (1 << k) - 1;
    printf("%d\n", (x & mask));
    return 0;
}
```

`(1 << k) - 1` 就是"k 个 1"的通用公式，详见本篇第六节的掩码生成。

#### 3、消除末尾五位

> 【例题3】给定一个 32 位整数，要求消除它的末五位。

消除末五位有两层含义：① 末五位全变成零；② 剩下的位不变。那么需要一个高 27 位全 1、低 5 位全 0 的数：

![[image-7907e791.png]]

但如果真这么写，代码不疯掉，人也会疯掉，所以一般转成十六进制——每 4 个二进制位对应 1 个十六进制数，得到 0xffffffe0：

```
#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0xffffffe0) );
    return 0;
}
```

提示：**f 代表 4 个 1；e 代表 3 个 1 和 1 个 0；0 代表 4 个 0**。

#### 4、消除末尾连续 1

> 【例题4】给出一个整数，将它的二进制表示里末尾连续的 1 都变成 0，输出改变后的数。

这个数的二进制形式一定是：

![[FjNYjX6GoiKRmv13CEGybKCt0Qe5-3f8f3223.png]]

把它加 1，得到：

![[FjFgw6gfXY6yEU2lGniGHpOVdaL4-150bac37.png]]

两数位与：

![[FivTjeFY443LOb1bqqNav9LkrIpD-abe123b7.png]]

代码实现：

```
#include <iostream>
using namespace std;

int modifyNumber(int number) {
    // 找到末尾连续1的长度
    int position = 0;
    while ((number & (1 << position)) != 0) {
        position++;
    }

    // 创建一个 k 位的掩码，将末尾连续的1置为0
    int mask = (1 << position) - 1;

    // 应用掩码到给定的数，将末尾连续的1置为0
    return number & ~mask;
}

int main() {
    int inputNumber = 55;
    int outputNumber = modifyNumber(inputNumber);
    cout << "Modified number: " << outputNumber << endl;
    return 0;
}
```

#### 5、2 的幂判定

> 【例题5】请用一句话，判断一个正数是不是 2 的幂。

如果一个数是 2 的幂，它的二进制表示必然是"1 后面跟一串 0"：

![[FuSMvHw-X3ZrceocHXM8XJQvjkY2-681fbd9f.png]]

将它减一（参考二进制减法的借位），得到：

![[Fp4a8QJapXNc0ry4bnQ3yEhYc5fY-7b87c143.png]]

这两个数位与的结果为零。所以答案为：

```
(x & (x-1)) == 0
```

## 三、或 |：置位与合并

### 3.1 规则与性质

| x | y | x \| y |
| --- | --- | --- |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |

两条结论：

1. 无论是 0 或 1，只要位或上 **1，就变成 1**
2. 只有当两个操作数都是 0 的时候，才变成 0

### 3.2 套路

**套路一：使得某一位或某几位为 1**

x | 0x01：

![[image-9c450db6.png]]

希望该数最右边的那个比特为 1——不管它原来是 0 还是 1，或上 1 后一定为 1。**与 0 或保留原样，与 1 或将该位变成 1。**

**套路二：把两个数拼起来**

0x00FF | 0xFF00：

![[image-7fff6177.png]]

0 和 1 互补的位模式相或，正好把两半拼成一个完整的数——这就是"合并"。

### 3.3 例题

#### 1、设置标记位

> 【例题1】给定一个数，将它二进制低位的第 5 位置为 1。

分析题意：如果第 5 位为 1，不用进行任何操作；如果为 0，则置为 1。言下之意，无论第 5 位是什么，直接置 1 即可：

```
#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | 0b10000);
    return 0;
}
```

#### 2、置空标记位

> 【例题2】给定一个数，将它二进制低位的第 5 位置为 0。

用刚学的位与可以这么写：

```
printf("%d\n", x & 0b11111111111111111111111111101111);
```

其它位不能变，所以位与上 1；第 5 位要置零，所以位与上 0。这样写有个问题：这串数字太长了，一点都不美观，而且容易写错（转成十六进制的过程也可能出错）。

位或只能把第 5 位**设置成 1**，怎么设置成 0 呢？可以配合减法，分成两步：

1. 首先，强行将低位的第 5 位置成 1
2. 然后，强行将低位的第 5 位去掉

第 (1) 步用位或，第 (2) 步直接用减法：

```
#include <stdio.h>
int main() {
    int x;
    int a = 0b10000;
    scanf("%d", &x);
    printf("%d\n", (x | a) - a );
    return 0;
}
```

> ⚠️ 注意：直接减是不行的！必须先或再减——首先要保证那一位为 1，否则贸然减会产生**借位**，把高位也改了，和题意不符。

（其实这题更顺手的写法是位与掩码：`x & ~(0b10000)`，掩码取反的套路见第六节。）

#### 3、低位连续零变一

> 【例题3】给定一个整数 x，将它低位连续的 0 都变成 1。

假设这个整数低位连续有 k 个零，二进制表示如下：

![[image-071ee475.png]]

对它进行减一操作，得到的二进制数就是：

![[image-02e82a1f.png]]

只要对这两个数进行位或，就能得到：

![[image-b8db44c7.png]]

正是题目所求：

```
#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | (x-1) );
    return 0;
}
```

## 四、异或 ^：翻转交换与加密

### 4.1 规则与性质

| x | y | x ^ y |
| --- | --- | --- |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |

三条重要性质：

1. **两个相同的数异或结果一定为 0**
2. 任何数和 0 异或结果是它本身；异或 1 就是它的相反值（该位翻转）
3. 异或运算满足**结合律和交换律**

一个数对一个值异或两次等于什么都没做：x ^ y ^ y → x。

![[image-10385f01.png]]

它就可以用来做简单的加密：先全部异或得到乱七八糟的东西，再异或回来得到想要的。也可以用来判断两个数是否相同。

### 4.2 swap 与数组逆序

利用"异或两次还原"还能写出这样的程序——不用临时变量交换两个数：

```
void swap(int *x, int *y)
{
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}
```

逐行追踪（设 *x = a，*y = b）：

| 语句 | *x | *y |
| --- | --- | --- |
| 初始 | a | b |
| `*y = *x ^ *y;` | a | a^b |
| `*x = *x ^ *y;` | a^(a^b) = b | a^b |
| `*y = *x ^ *y;` | b | b^(a^b) = (b^b)^a = a |

再基于这个 swap 还能实现数组逆序：

```
void swap_array(int a[], int cnt)
{
    int first, last;
    for(first=0, last=cnt-1; first<last; first++, last--)
        swap(&a[first], &a[last]);
}
```

> ⚠️ 注意是 `first < last` 而不是 `first <= last`：如果用了等号，奇数个数组单元时，中间那个数做的就是**自己与自己异或**，结果为 0。所以不加等号——奇数个时，中间那个数不做操作。

### 4.3 例题

#### 1、标记位取反

> 【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。

如果第 4 位为 1，让它异或上 0b1000 就变成 0；如果为 0，异或上 0b1000 就变成 1。无论如何都是异或上 0b1000：

```
#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x ^ 0b1000);
    return 0;
}
```

#### 2、变量交换

> 【例题2】给定两个数 a 和 b，用异或运算交换它们的值。

比较老的面试题了：

```
#include <stdio.h>
int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        a = a ^ b;   // (1)
        b = a ^ b;   // (2)
        a = a ^ b;   // (3)
        printf("%d %d\n", a, b);
    }
    return 0;
}
```

(1)(2) 两句相当于 b = a ^ b ^ b，根据异或的性质，b 已经变成原先 a 的值；第 (3) 句相当于 a = a ^ b ^ a，a 已经变成原先 b 的值。从而实现了 a 和 b 的交换。

#### 3、出现奇数次的数

> 【例题3】输入 n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个数。

两个一样的数异或结果为零——所有出现偶数次的数异或都抵消为 0。那么把这 n 个数都异或一下，剩下的就一定是出现奇数次的那个数：

```
#include <stdio.h>
int main() {
    int n, x, i, ans;
    scanf("%d", &n);
    ans = 0;
    for(i = 0; i < n; ++i) {
        scanf("%d", &x);
        ans = (ans ^ x);
    }
    printf("%d\n", ans);
    return 0;
}
```

#### 4、丢失的数

> 【例题4】给定 n-1 个数，分别代表 1 到 n 中缺了一个的序列，求丢失的那个数。

把给定的 n-1 个数和完整的 1 到 n 全部异或在一起——出现两次的都抵消，剩下的就是缺失的数：

```
#include <iostream>
#include <vector>
using namespace std;

// 找到缺失的数
int findMissingNumber(vector<int>& nums) {
    int n = nums.size() + 1;
    int xor_all = 0;  // 用于存储所有 1 到 n 的数的位异或结果
    int xor_n = 0;    // 用于存储给定的 n-1 个数的位异或结果

    // 计算 1 到 n 的所有数的位异或结果
    for (int i = 1; i <= n; i++) {
        xor_n ^= i;
    }

    // 计算给定的 n-1 个数的位异或结果
    for (int num : nums) {
        xor_all ^= num;
    }

    // 最终结果是两者的位异或结果，即缺失的数
    return xor_n ^ xor_all;
}

int main() {
    vector<int> nums = {1, 2, 4, 5};  // 假设缺失的数是3
    int missing_number = findMissingNumber(nums);
    cout << "缺失的数是: " << missing_number << endl;
    return 0;
}
```

#### 5、简单加密

基于**两个相同的数异或为零**、**任何数和零异或为其本身**这两个特点，异或还可以做简单加密：将明文异或上一个固定的数变成密文，继续异或上这个数，就把密文变回明文。

## 五、取反 ~：负数与加法技巧

### 5.1 单目运算与那个反直觉的 -2

取反是唯一的**单目**位运算符，只有一个操作数，表示为 ~x，对每一位按表取反：

| x | ~x |
| --- | --- |
| 1 | 0 |
| 0 | 1 |

```
#include <stdio.h>
int main() {
    int a = 0b1;
    printf("%d\n", ~a );
    return 0;
}
```

~a 代表对二进制数 1 取反，直观感受应该是 0。但实际输出的是：

> -2

为什么？因为这是一个 32 位整数，**前导零也要参与取反**：

```
~ 00000000 00000000 00000000 00000001
--------------------------------------
  11111111 11111111 11111111 11111110
```

对于一个有符号的 32 位整数，最高位代表符号位：最高位为 0 代表正数，为 1 代表负数。而这个 1111…1110 要按**补码**来解读（回顾 [[02-原码反码补码]]）：

### 5.2 补码的真实含义：互补成 2ⁿ

补码的真实含义，其实体现在"**补**"这个字上。在数学上，两个互为相反数的数字相加等于 0；而在计算机中，两个互为相反数的数字相加等于 **2 的 n 次方**。换言之，互为相反数的两个数**互补，补成 2 的 n 次**。

对于 32 位整型 n = 32；对于 64 位整型 n = 64：

![[FtYp9xvEhlduj1YtCnEf0vB1UBwf-b5077df0.png]]

于是，对于 int 类型：

![[Fv6q2Vd9LSbDZwSCdHhlaf6xKqP3-6a4699a3.png]]

即：

![[Fh68gYeZdzO0W4Dmw6pwnO02h09n-534bba65.png]]

于是我们开始数数：

```
2³²     = 1 00000000 00000000 00000000 00000000
2³² - 1 =   11111111 11111111 11111111 11111111
2³² - 2 =   11111111 11111111 11111111 11111110
```

进一步了解到 -2 的二进制表示。根据补码的定义，-2 = ~2 + 1，两步走：

1）对 2 的二进制按位取反：

```
~ 00000000 00000000 00000000 00000010
--------------------------------------
  11111111 11111111 11111111 11111101
```

2）然后加上 1：

```
  11111111 11111111 11111111 11111101
+ 00000000 00000000 00000000 00000001
--------------------------------------
  11111111 11111111 11111111 11111110
```

结果正好是开头 ~1 的结果——**(-2 = ~2 + 1)**，两种殊途同归。

### 5.3 套路：-x = ~x + 1

由 -2 = ~2 + 1 可知：

**-x = ~x + 1（这是一系列操作的核心，务必记住）**

然后，y 总讲的 **lowbit** 也是用到了这个。假设：

```
x    = 1010……1000……
~x   = 0101……0111……
~x+1 = 0101……1000……

x & (~x+1) = 0000……1000……
```

也就是**只保留从右边数第一个 1，其他全变成 0**。写成代码：

```
int lowbit(int x) {
    return x & -x;   // -x 就是 ~x+1，所以 x & -x 等价于 x & (~x+1)
}
```

利用这个性质可以求某个二进制序列中有多少个 1（一直循环直到 x 为 0）：

```
int res = 0;
while(x) {
    x -= lowbit(x);
    res++;
}
```

### 5.4 例题

#### 1、0 的取反

> 【例题1】0 的取反结果为多少呢？

对 0 取反：

```
~ 00000000 00000000 00000000 00000000
--------------------------------------
  11111111 11111111 11111111 11111111
```

按无符号看是 2³² - 1。但实际用 %d 输出时，你会发现它的值是 **-1**。为什么？因为 C 语言中 int 分 unsigned int 和 signed int，之前讨论的 int 都是 signed int 的简称。

**有符号整型**：输出采用 %d：

```
#include <stdio.h>
int main() {
    printf("%d\n", ~0 );
    return 0;
}
```

结果为 -1（1111…1111 按补码解读就是 -1）。

**无符号整型**：unsigned int 不需要符号位，32 位全部表示数值：

![[Fvrxl2rj6EjwUVfXT6rgAmcrhLlu-cdd113fb.png]]

输出采用 %u：

```
#include <stdio.h>
int main() {
    printf("%u\n", ~0 );
    return 0;
}
```

结果为 4294967295，即 2³² - 1。

**同一个位模式，两种解释**——又是 [[02-原码反码补码]] 那句话：变的只是解释这些位的方式。

#### 2、相反数

> 【例题2】给定一个 int 类型的正数 x，求 x 的相反数（不能用负号）。

直接利用核心公式 -x = ~x + 1：

```
#include <stdio.h>
int main() {
    int x = 18;
    printf("%d\n", ~x + 1 );
    return 0;
}
```

运行结果：-18。

#### 3、代替减法

> 【例题3】给定两个 int 类型的正数 x 和 y，实现 x - y（不能用减号）。

x - y = x + (-y)，而 -y = ~y + 1，所以减法可以用 **x + ~y + 1** 代替：

```
#include <stdio.h>
int main() {
    int a = 8;
    int b = 17;
    printf("%d\n", a + ~b + 1 );
    return 0;
}
```

运行结果：-9。

#### 4、代替加法

> 【例题4】给定两个 int 类型的正数 x 和 y，实现 x + y（不能用加号）。

把 x + y 变成 x - (-y)，而 -y 替换成 ~y + 1，所以 x + y 就变成了 **x - ~y - 1**：

```
#include <stdio.h>
int main() {
    int x = 18;
    int y = 7;
    printf("%d\n", x - ~y - 1 );
    return 0;
}
```

运行结果：25。

## 六、左移 <<：乘 2 与生成掩码

### 6.1 左移的二进制形态

x << y 念作"将 x 左移 y 位"（这里的位当然指二进制位）：先将 x 用二进制表示，然后左移 y 位，**尾部添上 y 个零**。

对于二进制数 (10111) 左移的结果：

![[image-53b57ad8.png]]

x << y 的执行结果等价于：

![[image-7ee8c389.png]]

如下代码：

```
#include <stdio.h>
int main() {
    int x = 3;
    int y = 5;
    printf("%d\n", x << y);
    return 0;
}
```

输出结果为 96，正好符合左移运算符的实际含义（3 × 2⁵ = 96）：

![[image-e0ccd2c0.png]]

最常用的就是当 x = 1 时：**1 << y 代表的就是 2^y**，即 2 的幂。

### 6.2 负数左移

x << y 中 x 为负数的情况：

```
#include <stdio.h>
int main() {
    printf("%d\n", -1 << 1);
    return 0;
}
```

输出为 -2，同样是满足的。用补码来解释：-1 的补码为：

![[image-5d5e3abf.png]]

左移一位后，最高位的 1 就没了，低位补上 0，得到：

![[image-6a1e305b.png]]

而这正好是 -2 的补码。继续左移 1 位，得到：

![[image-7204a479.png]]

这是 -4 的补码。以此类推，**负整数的左移结果同样满足乘 2 的规律**。可以理解成 -(x << y) 和 (-x) << y 是等价的。

### 6.3 左移负数位是什么情况

再试 y < 0 的情况：

```
#include <stdio.h>
int main() {
    printf("%d\n", 32 << -1);   // 16
    printf("%d\n", 32 << -2);   // 8
    printf("%d\n", 32 << -3);   // 4
    printf("%d\n", 32 << -4);   // 2
    printf("%d\n", 32 << -5);   // 1
    printf("%d\n", 32 << -6);   // 0
    printf("%d\n", 32 << -7);   // 0
    return 0;
}
```

虽然能够正常运行，但会报警告：

> [Warning] left shift count is negative [-Wshift-count-negative]

编译器告诉我们**尽量别在左移的时候用负数**。它的执行结果不能算错误（例子里结果都对，不会出现小数而是取整了），左移负数位其实效果和右移对应正数位一致——但这是**未定义行为**，不同编译器结果可能不同，别依赖它（总篇 6.2 也叮嘱过：移位不要用负数）。

### 6.4 左移时溢出会如何

int 类型是 32 位，最高位代表符号位。假设最高位为 1、次高位为 0，左移以后符号位会变成 0，会产生什么问题？

举个例子，对于 -2³¹ + 1，二进制表示为最高位和最低位为 1、其余为零：

```
#include <stdio.h>
int main() {
    int x = 0b10000000000000000000000000000001;
    printf("%d\n", x);          // -2147483647
    printf("%d\n", x << 1);     // ?
    return 0;
}
```

盲猜一下：最高位的 1 被移出去，最低位补上 0，结果应该是 0b10 = 2。实际输出的结果，的确是 **2**。

但如果按照"符号位"的规则，答案似乎应该是负数才对——这里又回到了补码的问题上。事实上，在计算机中 **int 整型其实是一个环**，溢出以后又会回来，而环的长度正好是 2³²，所以 -2³² + 2 = 2——有点像同余的概念，这两个数是模 2³² 同余的。

（其实跟之前遇见的"取一个十进制数的一位就除以 10"一样：二进制移一位就是乘除 2。运算器做乘除运算就是通过移位来进行的。）

### 6.5 应用

#### 1、取模转化成位运算

对于 x 模上一个 2 的次幂的数 y，可以转换成位与上 2^y - 1：

![[image-75c18240.png]]

在计算机中一行代码：`x & ((1 << y) - 1)`。

（为什么可行：2^y - 1 就是"y 个 1"，位与它等于只保留低 y 位，正好是模 2^y 的余数——和第二节的取末 K 位是同一个套路。）

#### 2、生成标记码

用左移实现标记码：**1 << k 作为第 k 个标记位的标记码**，一句话实现对标记位置 0、置 1、取反。

**1）标记位置 1** → 联想位或：

位或的特点是：位或上 1 结果为 1，位或上 0 结果不变。要求标记码第 k 位为 1、其它位为 0，正好是 (1 << k)：

```
x | (1 << k)
```

**2）标记位置 0** → 联想位与：

位与的特点是：位与上 0 结果为 0，位与上 1 结果不变。要求标记码第 k 位为 0、其它位为 1，即 ~(1 << k)：

```
x & ~(1 << k)
```

**3）标记位取反** → 联想异或：

异或的特点是：异或上 1 结果取反，异或上 0 结果不变：

```
x ^ (1 << k)
```

#### 3、生成掩码

用左移生成掩码，对某个数的二进制**末 k 位**执行操作：(1 << k) 是 1 加上 k 个 0，则 **(1 << k) - 1 就是 k 个 1**：

```
把末尾的 k 位都变成 1： x |  ((1 << k) - 1)
把末尾的 k 位都变成 0： x & ~((1 << k) - 1)
把末尾的 k 位都取反：   x ^  ((1 << k) - 1)
```

## 七、标记位三操作速查

| 想干的事 | 用哪个运算 | 表达式 |
| --- | --- | --- |
| 第 k 位置 1 | 或 | `x \| (1 << k)` |
| 第 k 位置 0 | 与 | `x & ~(1 << k)` |
| 第 k 位取反 | 异或 | `x ^ (1 << k)` |
| 末 k 位全置 1 | 或 + 掩码 | `x \| ((1 << k) - 1)` |
| 末 k 位全置 0 | 与 + 掩码 | `x & ~((1 << k) - 1)` |
| 末 k 位全取反 | 异或 + 掩码 | `x ^ ((1 << k) - 1)` |
| 取末 k 位 | 与 + 掩码 | `x & ((1 << k) - 1)` |
| 保留最低位的 1 | 取反 | `x & -x`（lowbit） |
| 判断 2 的幂 | 与 | `(x & (x-1)) == 0` |
| 判断奇偶 | 与 | `x & 1` |

## 八、盲点自测

1. **为什么 ~1 = -2 而不是 0？** ——32 位前导零也参与取反，得 1111…1110，按补码解读就是 -2。
2. **-x = ~x + 1 的原理？** ——补码的本质是互补成 2ⁿ：x + ~x = 1111…1111（全 1），再加 1 恰好溢出到 2ⁿ 归零。
3. **lowbit(x) 为什么等于 x & -x？** ——-x 就是 ~x+1，x & (~x+1) 恰好只保留最右边那个 1，其余位全部清零。
4. **(x | a) - a 置零某一位时，为什么不能直接 x - a？** ——如果那一位本来就是 0，直接减会发生借位，把高位也改了；先或置 1 再减就稳了。
5. **x & (x-1) == 0 为什么能判定 2 的幂？** ——2 的幂形如 100…0，减 1 后变成 011…1，两者没有共同的 1，位与必为 0。
6. **异或交换为什么不用临时变量？什么时候会翻车？** ——三次异或利用"异或两次还原"；翻车场景：同一变量自己和自己交换（x^x = 0），所以数组逆序用 first < last 跳过中间元素。
7. **32 << -1 为什么不建议写？** ——移位数为负是未定义行为，虽然很多环境表现为右移并取整，但可移植性没有保障。
8. **int 溢出后为什么像"绕回来"？** ——int 是一个长度 2³² 的环，溢出即模 2³² 同余；这也是补码时钟比喻的另一种说法。

---

至此三件套集齐：进制、补码、位运算。但"数"还差一块——小数怎么表示？→ [[04-浮点数]]

⬅️ [[02-原码反码补码|原码反码补码]] 🏠 [[00-信息的表示与处理]] ➡️ [[04-浮点数|浮点数]]