--- title: "信息的表示与处理" created: 2026-08-29 updated: 2026-08-27 aliases: - 信息的处理和表示 这一篇就够了 tags: - 基础与理论 - 信息的表示与处理 - CSAPP --- # 信息的表示与处理 > 本篇是「信息表示」的总篇（对应 CSAPP 第 2 章），三版旧笔记已合并为这一篇。 > 深入展开的子笔记按顺序：[[01-进制与进制转换]] → [[02-原码反码补码]] → [[03-位运算应用]]（与、或、异或、取反、左移五式合并） → [[04-浮点数]]（IEEE 754 掰开揉碎） → [[05-字符编码]]（ASCII → Unicode → UTF-8） ## 一、引言：为什么是二进制 ### 1.1 二进制的物理基础 现代计算机存储和处理的信息以**二值信号**来表示，这些微不足道的二进制数字，或者称为位（bit），形成了数字革命的基础。 对于拥有十个手指的人类来说，使用十进制表示法是件很自然的事情，但是在存储和处理信息的机器当中，二进制值工作得更好——二值信号能够很轻松地被表示、存储和传输： | 物理介质 | 状态 0 | 状态 1 | | --- | --- | --- | | 穿孔卡片 | 无洞 | 有洞 | | 导线电压 | 低电压 | 高电压 | | 磁盘 | 一个磁化方向 | 另一磁化方向 | | 晶体管 | 截止 | 导通 | > 💡 **关键理解**：单独的位没有什么作用，只有把位**组合**在一起，再加上某种**解释**，才能用来表示有限集合的元素。 （有个地狱冷笑话就是说把人的生死作为 0 和 1，通过反复电击控制生死传入 0 和 1，从而黑入生死谱 bushi） ### 1.2 有限表示的代价 计算机的表示法是用**有限数量的位**来对一个数字编码，因此，结果太大以至于不能表示时，某些运算就会**溢出**。 整数运算满足人们所熟知的许多性质，像交换律、结合律……浮点数则具有完全不同的数学特性，由于表示的精度有限，浮点运算是不能结合的： ``` (3.14 + 1e20) - 1e20 = 0.0 3.14 + (1e20 - 1e20) = 3.14 ``` | 特性 | 整数运算 | 浮点运算 | | --- | --- | --- | | 数值范围 | 相对较小 | 较大 | | 表示精度 | **精确** | **近似** | | 结合律 | ✅ 满足 | ❌ 不满足 | 整数运算和浮点数运算会有不同的数学属性，是因为它们处理数字表示有限性的方式不同——整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示是精确的；而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。 ### 1.3 连续与离散 在数学中（类似于极限吧）我们知道数是连续的，任给两个数，它们中间都存在无限多的数。但对于计算机来说，它不能连续地表达所有的数，只能用离散的数来表达某一个数。 ![[image-f4d3fde8.png]] 整数相对于浮点数来说其实是相当少的，所以对于这么少的而且好像很整齐的数，计算机可以做到很精确。 但浮点数很多，光是 0~1 中间就有无穷个数，肯定无法表示完全，中间一定有很多空缺的数。倘若它能表达浮点数 A 和浮点数 B，那么在浮点数 AB 中间的那些数是无法被表达的。 假若我们现在要的 -0.0049 就在 AB 中间： ![[image-34938f56.png]] 它就需要就近找一个计算机能表达的数，假使用 A 来表示它，所以我们得到的 -0.0049 并不是真正的 -0.0049，甚至可能用更长的一个数来表示： ![[image-9d3bd4ab.png]] 这就是浮点数的误差，与精度无关。如果把 float 换成 double，double 能表示更多的数，那么这相邻两个数之间的距离会小一点点，但也仅此而已： ![[image-4af62c76.png]] > 🖥️ 计算机：要这个数？？？额 没有，我给你一个比较接近的数吧 ## 二、信息存储基础 ### 2.1 位、字节与字 计算机中通常用 8 位的块（字节）作为最小的可寻址的内存单元。 | 单位 | 定义 | 说明 | | --- | --- | --- | | 位（bit） | 最小信息单位 | 取值为 0 或 1 | | 字节（byte） | 8 位 | 最小可寻址内存单元 | | 字（word） | 机器相关 | 32 位机器为 4 字节，64 位为 8 字节 | ``` 1 字节 = 8 位 取值范围：00000000 ~ 11111111（二进制） = 0 ~ 255（十进制） = 0x00 ~ 0xFF（十六进制） ``` 机器级程序将内存视为一个非常大的**字节数组**，称作虚拟内存。内存的每个字节都由一个唯一的数字来标识，称作它的**地址**，所有可能地址的集合称为**虚拟地址空间**——它只是一个展现给机器级程序的概念性映像，为程序提供一个看上去统一的字节数组。 #### 字长与地址空间 字的概念在计算机中很广泛，大到整个计算机的字长，再到一个程序以多少位编译，小到某个数据类型占据多少字节。 每台计算机都有一个**字长**，指明指针数据的标称大小。虚拟地址也是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小：对于一个字长为 w 的机器而言，虚拟地址的范围为 0 ~ 2^w-1，程序最多访问 2^w 个字节。 | 字长 | 虚拟地址范围 | 最大内存 | | --- | --- | --- | | 32 位 | 0 ~ 2³²-1 | 4 GB | | 64 位 | 0 ~ 2⁶⁴-1 | 16 EB | 机器和程序间具有一种向后兼容： - 若一个程序以 32 位编译，就可以在 32 位或 64 位机器上正确运行 - 若以 64 位编译，则只能在 64 位机器上正确运行 ### 2.2 进制系统 一个字节由八位组成，在二进制表示法中它的值域就是 0000 0000 ~ 1111 1111，这太过于冗长，而我们的十进制在这方面转换又比较复杂，于是可以用以 16 为基数的十六进制数来表示（hex，0x 开头）。这就得提到进制了——进制的概念、生活中的进制、以及全套转换方法（反复乘除法、简单拆分法），都整理在这篇里： 👉 **[[01-进制与进制转换]]** 这里只留最常用的对照表和速记： | 十进制 | 二进制 | 八进制 | 十六进制 | | --- | --- | --- | --- | | 0 | 0000 | 0 | 0 | | 1 | 0001 | 1 | 1 | | 2 | 0010 | 2 | 2 | | 3 | 0011 | 3 | 3 | | 4 | 0100 | 4 | 4 | | 5 | 0101 | 5 | 5 | | 6 | 0110 | 6 | 6 | | 7 | 0111 | 7 | 7 | | 8 | 1000 | 10 | 8 | | 9 | 1001 | 11 | 9 | | 10 | 1010 | 12 | A | | 11 | 1011 | 13 | B | | 12 | 1100 | 14 | C | | 13 | 1101 | 15 | D | | 14 | 1110 | 16 | E | | 15 | 1111 | 17 | F | > 💡 **记忆技巧**：记住 A=1010、C=1100、F=1111、4=0100、8=1000，其他可推导 #### 2 的幂次快速转换（特例速算） 当 x = 2^n 时，可以很容易地把 x 写成十六进制的形式。把 n 表示成 **n = i + 4j** 的形式（0 ≤ i ≤ 3），x 的十六进制就是：开头是 2^i 对应的十六进制数字（i=0→1，i=1→2，i=2→4，i=3→8），后面跟着 j 个 0。 ``` 2048 = 2¹¹ = 2^(3+4×2) → 8 后面跟 2 个 0 → 0x800 32768 = 2¹⁵ = 2^(3+4×3) → 8 后面跟 3 个 0 → 0x8000 反过来： 0x10000 = 1 后面跟 4 个 0 → 2^(0+4×4) = 2¹⁶ = 65536 ``` ### 2.3 C 语言数据类型大小 C 语言中的数据类型，所分配的字节数也是受程序是如何编译的影响而变化的： | 类型 | 32 位程序 | 64 位程序 | 说明 | | --- | --- | --- | --- | | `char` | 1 字节 | 1 字节 | 表示一个单独的字节 | | `short` | 2 字节 | 2 字节 | | | `int` | 4 字节 | 4 字节 | 即使在 64 位系统编译，通常也只有 4 字节 | | `long` | 4 字节 | **8 字节** | 表示一次传输的数据量，随程序位数变化 | | `long long` | 8 字节 | 8 字节 | | | 指针 | 4 字节 | **8 字节** | 等于字长 | | `float` | 4 字节 | 4 字节 | | | `double` | 8 字节 | 8 字节 | | 还有一个有无符号的概念：这些数据类型在编码时默认是有符号数值，加上 `unsigned` 前缀声明为无符号数。能表示的范围总量不变，若为有符号数则要分出一半表示负数，若为无符号数则全部用来表示正数部分，所能表示的正数也会更多。 ``` char c; // 有符号：-128 ~ 127 unsigned char uc; // 无符号：0 ~ 255 ``` 顺带一提，`char` 虽叫"字符"，存的也是数字——文字怎么变成 01，是另一条线的故事：👉 **[[05-字符编码]]** 那这些整数类型到底是怎么个事？👉 **[[02-原码反码补码]]** ### 2.4 寻址和字节顺序（大端小端） 一个程序、一个数组、一个数据类型，它们都占据了多个字节。对于这些跨越多字节的程序对象，需要建立两个规则——这个对象的地址是什么？在内存中如何排列这些字节？ 多字节对象都被存储为连续的字节序列，**对象的地址为所使用字节中的最小地址**。比如一个 int 变量 x 的地址为 0x100，也就是说地址表达式 &x 的值为 0x100，它的 4 个字节将被存储在内存的 0x100、0x101、0x102、0x103 的位置。 地址的问题解决了，那么在内存中是如何排列的呢？假使 x 中存放的值是 0x01234567： ![[image-fb57a01f.png]] ![[image-3ceeeba3.png]] 它拥有两种排列方式： 1. **大端法**：数据的低位保存在内存的高地址中，数据的高位保存在内存的低地址中（最高有效字节在最前面） 2. **小端法**：数据的低位保存在内存的低地址中，数据的高位保存在内存的高地址中（最低有效字节在最前面） ``` 地址: 0x100 0x101 0x102 0x103 大端法(Big): 01 23 45 67 ← 高位在低地址 小端法(Little): 67 45 23 01 ← 低位在低地址 ``` | 字节序 | 特点 | 典型使用 | | --- | --- | --- | | 大端法 | 符合人类阅读习惯 | 网络传输、部分处理器 | | 小端法 | 符合机器处理顺序 | x86、大多数个人电脑 | 我们常用的个人计算机都只用小端模式，其实本质无太大区别，只要选择了一种从一而终就不会出现什么问题。但**跨平台数据传输**时需要注意转换！ ## 三、整数表示 在 C 和 C++ 中，整数有两种方式编码：一种只能表示非负数（无符号），另一种能表示负数、0 和正数（有符号）。而 Java 只支持有符号数。完整的推导过程（为什么是补码、时钟理解、转换陷阱）在这里： 👉 **[[02-原码反码补码]]** 这里留主干。 ### 3.1 无符号数编码 将位向量解释为非负整数，直接按权展开（就是我们二进制转十进制的步骤）： ``` [1011] = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 2 + 1 = 11 ``` 取值范围：0 ~ 2^w - 1 ### 3.2 有符号数编码：原码 → 反码 → 补码 如何用二进制表示负数？历史提出了三种方案，一代一代都是为了解决上一代的坑： | 方案 | 思路 | 优点 | 缺点 | | --- | --- | --- | --- | | 原码 | 最高位当符号位（0 正 1 负） | 直观 | 负数计算出错，有 +0 和 -0 | | 反码 | 负数符号位不变其余取反 | 能正确计算负数 | 跨零计算出错，仍有两个零 | | 补码 | 反码 + 1 | 完美解决所有问题 | **现代计算机采用** | **补码的数学本质**：利用越界会丢失的特性，让 a + (-a) = 0。 ``` -1 的补码 = 1111 1111 验证：0000 0001 + 1111 1111 = 1 0000 0000 ↑ 溢出丢弃 = 0000 0000 ✓ 公式：负数 -a 的补码 = 2ⁿ - a（n 为位数） ``` 补码的最高位权重为**负**，其余位权重为正： ``` 例：[1011] 的补码值 = -1×2³ + 0×2² + 1×2¹ + 1×2⁰ = -8 + 0 + 2 + 1 = -5 ``` 有了补码最大的好处就是：做计算的时候不需要做符号判断，可以直接做简单的二进制加法。 ### 3.3 取值范围 | 类型 | 位数 | 最小值 | 最大值 | | --- | --- | --- | --- | | char | 8 | -128 | 127 | | short | 16 | -32768 | 32767 | | int | 32 | -2147483648 | 2147483647 | **为什么不对称？** 一半的位模式表示负数，另一半表示非负数，因为 0 占用了非负数的一个位置，所以能表示的正数比负数少一个：|Tmin| = Tmax + 1。 可以理解成一个时钟： ``` 127 ... | ... -1 ← 0 → 1 ... | ... -128 顺时针：127 + 1 = -128（正溢出） 逆时针：-128 - 1 = 127（负溢出） ``` 比最小的小就变成最大的，比最大的大就变成最小的（24 点过后不就是新的一天变成 1 点了）。 ### 3.4 有符号与无符号数的转换 **核心原则：底层位模式不变，改变的只是解释这些位的方式！** 就像存入一个数，这个数在内存里不会变，变的只是你用二进制还是十进制去解释它。 - 补码 → 无符号（T2U）：若 x ≥ 0 保持不变；若 x < 0，T2U(x) = x + 2^w - 无符号 → 补码（U2T）：若 u ≤ Tmax 保持不变；若 u > Tmax，U2T(u) = u - 2^w ``` 例（4位）： -5(补码) = 1011 → 作为无符号数 = 8 + 2 + 1 = 11 验证：-5 + 16 = 11 ✓ ``` #### ⚠️ C 语言中的陷阱 ``` // 陷阱1：比较时的隐式转换 int x = -1; unsigned u = 0; if (x < u) // -1 被转换为 4294967295，结果为 false！ printf("x < u"); // 陷阱2：无符号数循环 unsigned i; for (i = 10; i >= 0; i--) // 永远不会结束！ // 当 i=0 时，i-- 变成 4294967295 // 陷阱3：sizeof 返回无符号数 #define DELTA sizeof(int) for (i = n; i - DELTA >= 0; i -= DELTA) // i - DELTA 会被转为 unsigned ``` 执行一个运算时，一个运算数是有符号的而另一个为无符号的，C 语言会隐式地将参数强制类型转换成无符号数，并假设这两个数都是非负的再执行运算。这对于算术运算可能没多大差异，但是在关系运算中，会导致非直观的结果（-1 < 0U 是错的！最靠近 0 的负数会被映射成最大的无符号数）。 ## 四、整数运算 ### 4.1 无符号加法 ``` 对于 w 位无符号数 x + y： 若 x + y < 2^w：结果正常 若 x + y ≥ 2^w：溢出，结果 = x + y - 2^w ``` ``` 例（4位，范围0~15）： 1100 (12) + 0101 (5) ------- 10001 → 0001 (1) // 溢出丢弃最高位 检测溢出： unsigned s = x + y; if (s < x) // 发生溢出 ``` ### 4.2 补码加法 ``` 正溢出：两个大正数相加，结果变成负数 负溢出：两个大负数相加，结果变成正数 例（4位补码，范围 -8 ~ 7）： 0111 (7) 1000 (-8) + 0001 (1) + 1111 (-1) ------- -------- 1000 (-8) ❌ 0111 (7) ❌ 检测： // 正溢出：x > 0 且 y > 0，但 s ≤ 0 // 负溢出：x < 0 且 y < 0，但 s ≥ 0 ``` ### 4.3 补码取负 ``` -x 的补码 = ~x + 1 特例： -0 = 0（正常） -Tmin = Tmin（溢出！因为 Tmax + 1 = Tmin） ``` ### 4.4 乘法与除法 乘法截断：取结果的低 w 位（无符号 `(x × y) mod 2^w`）。运算器做乘除运算就是通过移位来进行的： ``` x * 16 = x << 4 x * 14 = x * 16 - x * 2 = (x << 4) - (x << 1) ``` 除法截断：正数向下取整（7 / 2 = 3），负数向零舍入（-7 / 2 = -3，不是 -4！）。 ## 五、浮点数表示（IEEE 754） 这一章是速查表；0.1 为什么存不精确、Bias 为什么是 127、对阶怎么回事的完整版在 👉 **[[04-浮点数]]** ### 5.1 为什么需要浮点数？ ``` 整数的局限： 32 位整数最大约 2×10⁹ 无法表示 6.02×10²³（阿伏伽德罗常数） 无法表示 1.6×10⁻¹⁹（电子电荷） 解决方案：科学计数法思想 V = (-1)^s × M × 2^E s: 符号位（Sign） M: 尾数（Mantissa），决定精度 E: 指数（Exponent），决定范围 ``` ### 5.2 IEEE 754 格式 ``` 单精度 float（32位）： ┌──────┬──────────┬───────────────────────┐ │ 1位 │ 8位 │ 23位 │ │ s │ exp │ frac │ │符号位│ 指数域 │ 尾数域 │ └──────┴──────────┴───────────────────────┘ 双精度 double（64位）： ┌──────┬───────────┬────────────────────────────────────┐ │ 1位 │ 11位 │ 52位 │ └──────┴───────────┴────────────────────────────────────┘ ``` ### 5.3 三种情况 **规格化值**（exp 既不全 0 也不全 1）： ``` E = exp - Bias（偏置值） float: Bias = 127，double: Bias = 1023 M = 1.frac（隐含的前导1） V = (-1)^s × 2^E × M ``` 示例：将 12.375 转换为 float ``` 1. 转为二进制：12.375 = 1100.011 2. 规格化：1.100011 × 2³ 3. 确定各部分： s = 0（正数） E = 3，exp = E + 127 = 130 = 1000 0010 frac = 100011（补零到23位） 4. 结果：0 10000010 10001100000000000000000 = 0x41460000 ``` **非规格化值**（exp 全 0）：E = 1 - Bias，M = 0.frac（无隐含 1）。用来表示 0（+0 和 -0，比较时相等）和非常接近 0 的数（渐进下溢）。 **特殊值**（exp 全 1）： ``` 无穷大（frac = 0）：1.0/0.0、溢出 产生 NaN（frac ≠ 0）：√(-1)、0.0/0.0、∞-∞ 产生 ``` ### 5.4 浮点数特性 | 类型 | 最小正规格化数 | 最大有限数 | 精度（有效数字） | | --- | --- | --- | --- | | float | ≈1.2×10⁻³⁸ | ≈3.4×10³⁸ | 约 7 位十进制 | | double | ≈2.2×10⁻³⁰⁸ | ≈1.8×10³⁰⁸ | 约 16 位十进制 | 浮点数分布不均匀：越靠近 0，可表示的数越密集；越远离 0，相邻两个浮点数的间隔越大。 ### 5.5 舍入规则 IEEE 754 默认使用**向偶数舍入**：当恰好在中间时，舍入到最近的偶数（1.5 → 2，2.5 → 2，3.5 → 4）。为什么？统计上更公平，避免累积误差。 ### 5.6 浮点数运算注意事项 ``` // 不满足结合律 (3.14 + 1e20) - 1e20 // = 0.0 3.14 + (1e20 - 1e20) // = 3.14 // 不满足分配律 1e20 * (1e20 - 1e20) // = 0.0 1e20 * 1e20 - 1e20 * 1e20 // = NaN（∞ - ∞） // 比较问题 0.1 + 0.2 == 0.3 // false! // 正确的比较方式 #define EPSILON 1e-9 fabs(a - b) < EPSILON // 判断 a ≈ b ``` ## 六、位运算 二进制值是计算机编码、存储和操作信息的核心，所以围绕数组 0、1 的研究已经演化出了丰富的数学知识体系——这起源于 1850 年前后乔治·布尔（George Boole）的工作，因此得名**布尔代数**。将真（true）、假（false）编码模拟二进制值 1、0，设计出一种代数（离散数学那套逻辑差不多）。 ![[image-4270d0ea.png]] 对于颜色表示 RGB 也同样可以使用布尔代数：光是基于光源 R、G、B 的开、关（1、0），就能创造八种颜色，再将每种颜色用一个长度为 3 的位向量来表示，以进行布尔运算： ![[image-a2c76ed8.png]] ``` 蓝色|绿色 黄色&蓝绿色 红色^红紫色 001 110 100 |010 & 011 ^ 101 ---- ---- ---- 011 010 001 蓝绿色 绿色 蓝色 ``` C 语言被称作最接近底层的语言，原因之一是它提供很多接近底层的操作，比如它**支持按位进行布尔运算**：`&` 与、`|` 或、`~` 取反、`^` 异或、`<<` 左移、`>>` 右移。 确定一个位级表达式的结果的最好的方法，就是把十六进制的参数拓展成二进制表示，并执行二进制运算，然后再转换回十六进制： ``` ~0x41 → ~[0100 0001] → [1011 1110] → 0xBE ``` ### 6.1 四种布尔位运算 | 运算 | 规则 | 应用篇 | | --- | --- | --- | | 与 `&` | 同真为真，其余为假 | [[03-位运算应用]] | | 或 `\|` | 同假为假，其余为真 | [[03-位运算应用]] | | 异或 `^` | 相同为 0，不同为 1 | [[03-位运算应用]] | | 取反 `~` | 0 变 1，1 变 0 | [[03-位运算应用]] | 异或的重要性质（算法里常用）： ``` x ^ 0 = x // 与0异或不变 x ^ x = 0 // 与自身异或为0 x ^ y ^ y = x // 异或两次还原 ``` ### 6.2 移位运算 **左移 `<<`**：将二进制的末尾添加 y 个零，就好比向左移动了 y 位。 ``` x << k // 相当于 x × 2^k（不溢出时） 1 << n // 2 的 n 次幂 ``` **右移 `>>`**：从右边开始截掉 y 个数。因为右移会涉及到符号位，如果是有符号数移动也补 0 的话，就从负变成正了，显然不合理： | 类型 | 填充方式 | 名称 | | --- | --- | --- | | 无符号数 | 左边补 **0** | 逻辑右移 | | 有符号数 | 左边补 **符号位** | 算术右移 | ``` x >> k // 相当于 x ÷ 2^k（向下取整） ``` 其实就简单认为：无符号数补 0，有符号数补符号位就行了。C 语言并没有明确定义对有符号数进行哪种右移，这可能出现可移植性的问题，但实际上所有编译器和机器组合都对有符号数进行算术右移。在 Java 中对于右移有着更明确的定义：`x>>k` 表示算术右移，`x>>>k` 表示逻辑右移——这也是为什么要多此一举引出逻辑、算术右移的概念的原因。 **注意事项**： ``` // ❌ 移位的时候不要用负数，这是没有定义的行为 x << -2 // !!NO!! // ⚠️ 优先级：加减的优先级要比移位运算来得高 1 << 2 + 3 << 4 // 实际是 (1 << (2+3)) << 4 (1 << 2) + (3 << 4) // 拿不准的时候，根据本意加上括号 // 结合性：自左向右可结合 x << j << k // 等价于 (x << j) << k ``` ### 6.3 逻辑运算？按位运算？ 对于逻辑运算来说，它只看到整数有两个值，要么是 0 要么是 1，所以非 0 的值都认为是 1。可以理解为**逻辑运算是把所有非 0 值都变成 1，然后做按位运算**。因为实际上在计算机里头只有按位计算，C 语言中的逻辑运算只是加以封装后的形式： ``` 5 & 4 → 4 5 && 4 → 1 → 1 & 1 → 1 5 | 4 → 5 5 || 4 → 1 → 1 | 1 → 1 ~4 → -5 !4 → !1 → ~1 → 0 ``` | | 位运算 | 逻辑运算 | | --- | --- | --- | | 运算符 | `&` `\|` `~` `^` | `&&` `\|\|` `!` | | 操作对象 | 每一个二进制位 | 整个值（非 0 视为真） | | 返回值 | 位运算结果 | 0 或 1 | | 短路求值 | ❌ 无 | ✅ 有（1\|\|任意 为 1，0&&任意 为 0） | 可以使用位级和逻辑运算写出一个表达式，等价于 x==y（相等时返回 1，否则返回 0）：两个相同的数做异或结果是 0，所以 `x^y` 返回 0 时相等——希望的是相等时得 1，所以再来个 `!`： ``` !(x ^ y) // 相等得1，不相等得0 ``` ### 6.4 位运算技巧汇总 | 操作 | 表达式 | 说明 | | --- | --- | --- | | 获取第 k 位 | `(x >> k) & 1` | | | 设置第 k 位为 1 | `x \| (1 << k)` | | | 清除第 k 位 | `x & ~(1 << k)` | | | 翻转第 k 位 | `x ^ (1 << k)` | | | 判断奇偶 | `x & 1` | 0 偶 1 奇 | | 判断 2 的幂 | `x & (x-1) == 0` | 需 x>0 | | 取最低位的 1 | `x & (-x)` | lowbit | | 清除最低位的 1 | `x & (x-1)` | | | 判断相等 | `!(x ^ y)` | | | 交换两数 | `a^=b; b^=a; a^=b;` | | | 统计 1 的个数 | 见下方代码 | Brian Kernighan 算法 | ``` // 统计二进制中 1 的个数 int count = 0; while (x) { x &= (x - 1); // 清除最低位的1 count++; } // 打印二进制（没有现成的 % 格式能输出二进制，自己造一个） int number; scanf("%i", &number); // %i 能自动识别进制：0 开头八进制，0x 开头十六进制 unsigned mask = 1u << 31; // 从最高位开始，左移31比特就是 0x8000……0000 for (; mask; mask >>= 1) { printf("%d", (number & mask) ? 1 : 0); } ``` 位域操作（比如 RGB 颜色）： ``` #define GET_R(c) (((c) >> 16) & 0xFF) #define GET_G(c) (((c) >> 8) & 0xFF) #define GET_B(c) ((c) & 0xFF) #define MAKE_RGB(r,g,b) (((r)<<16) | ((g)<<8) | (b)) ``` 这些技巧的推导过程和刷题实战，都展开在 [[03-位运算应用]] 里，算法区的延伸见 [[位运算相关问题|位运算相关问题]]。 ## 七、可移植性与最佳实践 ### 7.1 固定宽度类型 使用 `` 中的类型确保跨平台一致性： ``` int8_t / uint8_t // 精确 8 位 int16_t / uint16_t // 精确 16 位 int32_t / uint32_t // 精确 32 位 int64_t / uint64_t // 精确 64 位 ``` ### 7.2 常见陷阱总结 | 陷阱 | 示例 | 解决方案 | | --- | --- | --- | | 有无符号混用 | `-1 < 0U` 为假 | 避免混用，或显式转换 | | 无符号回绕 | `for(u=n; u>=0; u--)` 死循环 | 使用有符号数 | | 移位未定义 | `1 << 32` 或 `x << -1` | 确保 0 ≤ k < 位宽 | | 浮点比较 | `0.1 + 0.2 == 0.3` | 使用误差范围比较 | | 整数溢出 | `INT_MAX + 1` | 检查边界条件 | | 优先级错误 | `1 << 2 + 3` | 使用括号明确优先级 | ## 八、知识图谱 ``` 信息的表示与处理 │ ├── 信息存储基础 │ ├── 位、字节、字 │ ├── 进制系统 → [[01-进制与进制转换]] │ └── 字节顺序（大端/小端） │ ├── 整数表示 → [[02-原码反码补码]] │ ├── 无符号编码（直接二进制） │ ├── 有符号编码：原码 → 反码 → 补码★ │ ├── 有无符号转换 │ └── 取值范围与溢出 │ ├── 整数运算 │ ├── 加法与溢出检测 │ ├── 取负（~x + 1） │ └── 乘除法（移位优化） │ ├── 浮点数表示（IEEE 754）→ [[04-浮点数]] │ ├── 格式：符号位 + 指数域 + 尾数域 │ ├── 规格化 / 非规格化 / 特殊值（∞, NaN） │ ├── 舍入规则（向偶数舍入） │ └── 运算特性（不满足结合律） │ ├── 位运算 → [[03-位运算应用]] │ ├── 与 &（掩码与清位） │ ├── 或 |（置位与合并） │ ├── 异或 ^（翻转交换与加密） │ ├── 取反 ~（负数与加法技巧） │ └── 左移 <<（乘2与生成掩码） │ └── 字符编码 → [[05-字符编码]] ├── ASCII：7 位 128 字符，'0'=48 / 'A'=65 ├── 各国造表：GB2312 / GBK / Big5 → 码位冲突=乱码根源 ├── Unicode：码点身份证（'中'=U+4E2D） └── UTF-8：变长 1-4 字节，ASCII 兼容 + 自同步 ``` ## 参考资料 - 《深入理解计算机系统》(CSAPP) 第 2 章 - IEEE 754-2019 浮点数标准 - 《Hacker's Delight》位运算技巧 - 阮一峰《字符编码笔记》：`https://www.ruanyifeng.com/blog/2007/10/ascii_unicode_and_utf-8.html` ⬅️ [[05-关于二维码]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[01-进制与进制转换]]