--- title: "01-计算机基础——信息表示" created: 2026-01-09 tags: - 博客 --- # 计算机基础——信息表示 ![[计算机信息表示深度解析-897921e0.png]] ## **一、引言：为什么是二进制** ### **1.1 二进制的物理基础** 现代计算机存储和处理的信息以**二值信号**来表示。这些微不足道的二进制数字，或者称为**位（bit）**，形成了数字革命的基础。 对于拥有十个手指的人类来说，使用十进制是很自然的事情。但在计算机中，**二进制值**工作得更好——二值信号能够很容易地被表示、存储和传输： | **物理介质** | **状态0** | **状态1** | | --- | --- | --- | | 穿孔卡片 | 无洞 | 有洞 | | 导线电压 | 低电压 | 高电压 | | 磁盘 | 一个磁化方向 | 另一磁化方向 | | 晶体管 | 截止 | 导通 | > *💡 **关键理解**：单独的位没有意义，只有把位**组合**在一起，再加上某种**解释规则**，才能表示有限集合的元素。* ### **1.2 有限表示的代价** 计算机用**有限数量的位**来编码数字，这导致： - 结果太大时会发生**溢出** - 整数运算和浮点运算具有不同的数学特性 | **特性** | **整数运算** | **浮点运算** | | --- | --- | --- | | 数值范围 | 相对较小 | 较大 | | 表示精度 | **精确** | **近似** | | 溢出问题 | 存在 | 存在 | | 结合律 | ✅ 满足 | ❌ 不满足 | **浮点数不满足结合律的例子：** ``` (3.14 + 1e20) - 1e20 // 结果：0.0 3.14 + (1e20 - 1e20) // 结果：3.14 ``` ### **1.3 连续与离散** 在数学中，实数是**连续**的——任意两个数之间都存在无穷多个数。但计算机只能用**离散**的、有限的位模式来表示数值。 ``` 数学世界： ←——————————————————————→ 连续无穷 计算机： • • • • • • 离散有限 ↑ 只能表示这些"格点"上的值 ``` **形象理解：** - 整数较少且"整齐"，计算机可以精确表示 - 浮点数太多（仅 0~1 之间就有无穷个），必然有"空缺" - 如果需要的值刚好在两个可表示的数之间，计算机只能用**最接近的可表示值**来替代 > *🖥️ **计算机内心OS**：你要这个数？没有诶...我给你一个比较接近的吧~* --- ## **二、信息存储基础** ### **2.1 位、字节与字** #### **基本单位** | **单位** | **定义** | **说明** | | --- | --- | --- | | 位（bit） | 最小信息单位 | 取值为 0 或 1 | | 字节（byte） | 8 位 | 最小可寻址内存单元 | | 字（word） | 机器相关 | 32位机器为4字节，64位为8字节 | ``` 1 字节 = 8 位 取值范围：00000000 ~ 11111111（二进制） = 0 ~ 255（十进制） = 0x00 ~ 0xFF（十六进制） ``` #### **虚拟内存模型** - 机器级程序将内存视为一个巨大的**字节数组** - 每个字节有唯一的**地址**（一个数字标识） - 所有可能地址的集合称为**虚拟地址空间** #### **字长与地址空间** **字长（Word Size）** 指明指针数据的标称大小，决定了虚拟地址空间的最大范围。 | **字长** | **虚拟地址范围** | **最大内存** | | --- | --- | --- | | 32位 | 0 ~ 2³²-1 | 4 GB | | 64位 | 0 ~ 2⁶⁴-1 | 16 EB | **程序编译的兼容性：** - 32位编译 → 可在32位/64位机器运行 - 64位编译 → 只能在64位机器运行 ### **2.2 进制系统** #### **为什么需要不同进制？** - **二进制**：计算机内部表示，但对人类太冗长 - **十进制**：人类习惯，但与二进制转换复杂 - **十六进制**：折中方案，4位二进制 = 1位十六进制 - **八进制**：3位二进制 = 1位八进制，某些场景使用 #### **进制对照表** | **十进制** | **二进制** | **八进制** | **十六进制** | | --- | --- | --- | --- | | 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.3 进制转换方法** #### **转换方法总览** ``` ←——— 反复除法 ——— ↗ ↘ 十进制 ←— 按权展开 —→ 二/八/十六进制 ↖ ↙ ←——— 反复乘法 ——— (小数部分) 二进制 ←——— 每4位一组 ———→ 十六进制 二进制 ←——— 每3位一组 ———→ 八进制 ``` #### **十进制 → 其他进制（反复除法）** **核心思想**：反复除以目标进制，记录余数，逆序排列 **例1：45(D) → 二进制** ``` 45 ÷ 2 = 22 ... 1 ↑ 22 ÷ 2 = 11 ... 0 │ 11 ÷ 2 = 5 ... 1 │ 逆序读取 5 ÷ 2 = 2 ... 1 │ 2 ÷ 2 = 1 ... 0 │ 1 ÷ 2 = 0 ... 1 │ 结果：45(D) = 101101(B) ``` **例2：314156(D) → 十六进制** ``` 314156 ÷ 16 = 19634 ... 12(C) ↑ 19634 ÷ 16 = 1227 ... 2 │ 1227 ÷ 16 = 76 ... 11(B) │ 逆序读取 76 ÷ 16 = 4 ... 12(C) │ 4 ÷ 16 = 0 ... 4 │ 结果：314156(D) = 4CB2C(H) ``` #### **其他进制 → 十进制（按权展开）** **核心思想**：每位数字 × 对应权重，求和 **例1：101101(B) → 十进制** ``` 101101(B) = 1×2⁵ + 0×2⁴ + 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 32 + 0 + 8 + 4 + 0 + 1 = 45(D) ``` **例2：7AF(H) → 十进制** ``` 7AF(H) = 7×16² + 10×16¹ + 15×16⁰ = 1792 + 160 + 15 = 1967(D) ``` #### **二进制 ↔ 十六进制（直接转换）** **核心技巧**：4位二进制 = 1位十六进制 ``` 二进制 → 十六进制：从右向左，每4位一组 1101 0011 1010 1111 D 3 A F → 0xD3AF 十六进制 → 二进制：每位展开为4位 0x5B = 0101 1011 5 B ``` #### **二进制 ↔ 八进制（直接转换）** **核心技巧**：3位二进制 = 1位八进制 ``` 二进制 → 八进制：从右向左，每3位一组 011 111 000 010 3 7 0 2 → 3702(O) 八进制 → 二进制：每位展开为3位 752(O) = 111 101 010 7 5 2 ``` #### **2的幂次快速转换** 当 x = 2ⁿ 时，有快速方法： 将 n 表示为 **n = i + 4j**（其中 0 ≤ i ≤ 3） - 十六进制为：2^i 后面跟 j 个 0 | **i** | **2^i (十六进制)** | | --- | --- | | 0 | 1 | | 1 | 2 | | 2 | 4 | | 3 | 8 | ``` 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 ``` #### **进制转换程序实现** **十进制 → 二进制输出** ``` #include int main() { int number; scanf("%d", &number); unsigned mask = 1u << 31; // 从最高位开始 int cnt = 0; for (; mask; mask >>= 1) { printf("%d", (number & mask) ? 1 : 0); cnt++; if (cnt % 4 == 0) printf(" "); // 每4位一个空格 } printf("\n"); return 0; } ``` > *💡 使用* `%i` *读取可以自动识别进制：* `0x` *开头为十六进制，*`0` *开头为八进制* ### **2.4 C语言数据类型大小** | **类型** | **32位程序** | **64位程序** | **说明** | | --- | --- | --- | --- | | `char` | 1 字节 | 1 字节 | 单个字节 | | `short` | 2 字节 | 2 字节 | | | `int` | 4 字节 | 4 字节 | 通常固定 | | `long` | 4 字节 | **8 字节** | 随程序位数变化 | | `long long` | 8 字节 | 8 字节 | | | `指针` | 4 字节 | **8 字节** | 等于字长 | | `float` | 4 字节 | 4 字节 | | | `double` | 8 字节 | 8 字节 | | **有符号与无符号：** ``` char c; // 有符号：-128 ~ 127 unsigned char uc; // 无符号：0 ~ 255 ``` > *总共能表示 256 个值，区别在于如何"分配"给正负数。* ### **2.5 字节顺序（大端 vs 小端）** 对于跨越多字节的对象，需要确定： 1. **地址**：使用最小字节的地址 2. **排列顺序**：高位在前还是低位在前？ 假设 `int x = 0x01234567`，地址为 `0x100`： ``` 地址: 0x100 0x101 0x102 0x103 大端法(Big): 01 23 45 67 ← 高位在低地址 小端法(Little): 67 45 23 01 ← 低位在低地址 ``` | **字节序** | **特点** | **典型使用** | | --- | --- | --- | | 大端法 | 符合人类阅读习惯 | 网络传输、部分处理器 | | 小端法 | 符合机器处理顺序 | x86、大多数个人电脑 | > *💡 只要保持一致，选择哪种并无本质区别。但**跨平台数据传输**时需要注意转换！* ## **三、整数表示** ### **3.1 无符号数编码** 将位向量解释为非负整数，直接按权展开： \(B^2 U\_w(\vec{x}) = \sum\_{i=0}^{w-1} x\_i \cdot 2^i\) **示例（4位）：** ``` [1011] = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 2 + 1 = 11 ``` **取值范围：** 0 ~ 2^w - 1 ### **3.2 有符号数编码** #### **问题的提出** 如何用二进制表示负数？历史上提出了三种方案： | **方案** | **思路** | **优点** | **缺点** | | --- | --- | --- | --- | | 原码 | 用一位表示符号 | 直观 | 计算需额外判断符号，有+0和-0 | | 反码 | 负数按位取反 | 可直接计算负数 | 跨零计算有问题，仍有两个零 | | 补码 | 反码 + 1 | 完美解决所有问题 | **现代计算机采用** | #### **原码** **定义**：最高位是符号位（0正1负），其余位为绝对值的二进制 ``` +7 = 0000 0111 -7 = 1000 0111 ``` **问题**：负数计算错误 ``` 计算 -56 - 1： 1 0111000 (-56) - 1 ----------- 1 0110111 = -55 ❌ (应该是-57) ``` #### **反码** **定义**：正数不变，负数符号位不变，其余位取反 ``` +7 = 0000 0111 -7 = 1111 1000 ``` **改进**：可以正确计算负数 ``` 计算 -56 - 1： -56 原码: 1 0111000 → 反码: 1 1000111 1 1000111 - 1 ----------- 1 1000110 = -57 的反码 ✓ ``` **问题**：跨零计算仍然错误 ``` 计算 -3 + 5： 1111 1100 (-3的反码) + 0000 0101 (5) ----------- 0000 0001 = 1 ❌ (应该是2) ``` #### **补码（现代计算机采用）** **定义**：正数不变，负数 = 反码 + 1 ``` +7 = 0000 0111 -7 = 1111 1001 ``` **数学本质**：利用溢出特性，让 a + (-a) = 0 ``` -1 的补码 = 1111 1111 验证：0000 0001 + 1111 1111 = 1 0000 0000 ↑ 溢出丢弃 = 0000 0000 ✓ 公式：负数 -a 的补码 = 2ⁿ - a（n为位数） 例：-1 的补码 = 2⁸ - 1 = 256 - 1 = 255 = 1111 1111 ``` **验证跨零计算：** ``` 计算 -3 + 5： -3 的补码: 1111 1101 1111 1101 + 0000 0101 ----------- 0000 0010 = 2 ✓ ``` #### **补码的数学表示** B2Tw(x⃗)=−xw−1⋅2w−1+∑i=0w−2xi⋅2i \(B\_2 T\_w(\vec{x}) = -x\_{w-1} \cdot 2^{w-1} + \sum\_{i=0}^{w-2} x\_i \cdot 2^i\) 最高位权重为**负**，其余位权重为正。 ``` 例：[1011] 的补码值 = -1×2³ + 0×2² + 1×2¹ + 1×2⁰ = -8 + 0 + 2 + 1 = -5 ``` #### **三种编码对比（8位）** | **十进制** | **原码** | **反码** | **补码** | | --- | --- | --- | --- | | +7 | 0000 0111 | 0000 0111 | 0000 0111 | | +1 | 0000 0001 | 0000 0001 | 0000 0001 | | +0 | 0000 0000 | 0000 0000 | 0000 0000 | | -0 | 1000 0000 | 1111 1111 | (不存在) | | -1 | 1000 0001 | 1111 1110 | **1111 1111** | | -7 | 1000 0111 | 1111 1000 | 1111 1001 | | -128 | (溢出) | (溢出) | **1000 0000** | #### **快速求补码** **方法一：取反加一** ``` -5 的补码： 5 的原码：0000 0101 取反： 1111 1010 加一： 1111 1011 ← -5 的补码 ``` **方法二：从右往左找第一个1，该位左边全部取反** ``` -12 → 12 = 0000 1100 ↑ 第一个1 结果：1111 0100 ← -12 的补码 ``` ### **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 (负溢出) ``` ### **3.4 有符号与无符号数的转换** #### **核心原则** **底层位模式不变，只是解释方式改变！** #### **转换公式** **补码 → 无符号（T2U）：** - 若 x ≥ 0：T2U(x) = x - 若 x < 0：T2U(x) = x + 2^w **无符号 → 补码（U2T）：** - 若 u ≤ Tmax：U2T(u) = u - 若 u > Tmax：U2T(u) = u - 2^w ``` 例（4位）： -5(补码) = 1011 作为无符号数 = 8 + 2 + 1 = 11 验证：-5 + 16 = 11 ✓ 14(无符号) = 1110 作为补码 = -8 + 4 + 2 = -2 验证：14 - 16 = -2 ✓ ``` #### **C语言中的转换** ``` // 显式转换 int tx = -1; unsigned ux = (unsigned)tx; // ux = 4294967295 // 隐式转换 int ty = -1; unsigned uy = ty; // 自动转换 // printf 中的转换 int x = -1; printf("x = %u = %d\n", x, x); // x = 4294967295 = -1 ``` #### **⚠️ 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) int i; for (i = n; i - DELTA >= 0; i -= DELTA) // 问题！ // i - DELTA 会被转为 unsigned ``` ## **四、整数运算** ### **4.1 无符号加法** ``` 对于 w 位无符号数 x + y： 若 x + y < 2ʷ：结果正常 若 x + y ≥ 2ʷ：溢出，结果 = x + y - 2ʷ ``` ``` 例（4位，范围0~15）： 1100 (12) + 0101 (5) ------- 10001 → 0001 (1) // 溢出丢弃最高位 12 + 5 = 17 → 17 - 16 = 1 ✓ ``` **检测溢出：** ``` unsigned s = x + y; if (s < x) // 发生溢出 ``` ### **4.2 补码加法** ``` 正溢出：两个大正数相加，结果变成负数 负溢出：两个大负数相加，结果变成正数 ``` ``` 例（4位补码，范围 -8 ~ 7）： 正溢出： 0111 (7) + 0001 (1) ------- 1000 (-8) // 7 + 1 = -8 ❌ 负溢出： 1000 (-8) + 1111 (-1) ------- 10111 → 0111 (7) // -8 + (-1) = 7 ❌ ``` **检测溢出：** ``` int s = x + y; // 正溢出：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 乘法与除法** **乘法截断：** ``` 无符号乘法：(x × y) mod 2ʷ 补码乘法：U2T((x × y) mod 2ʷ) 即：取结果的低 w 位 ``` **乘法优化（乘以2的幂用左移）：** ``` x * 16 = x << 4 x * 14 = x * 16 - x * 2 = (x << 4) - (x << 1) ``` **除法截断：** ``` 正数向下取整：7 / 2 = 3 负数向零舍入：-7 / 2 = -3（不是 -4！） ``` --- ## **五、浮点数表示（IEEE 754）** ### **5.1 为什么需要浮点数？** ``` 整数的局限： 32位整数最大约 2×10⁹ 无法表示 6.02×10²³（阿伏伽德罗常数） 无法表示 1.6×10⁻¹⁹（电子电荷） 解决方案：科学计数法思想 V = (-1)ˢ × M × 2ᴱ s: 符号位（Sign） M: 尾数（Mantissa），决定精度 E: 指数（Exponent），决定范围 ``` ### **5.2 IEEE 754 格式** ``` 单精度 float（32位）： ┌──────┬──────────┬───────────────────────┐ │ 1位 │ 8位 │ 23位 │ │ s │ exp │ frac │ │符号位│ 指数域 │ 尾数域 │ └──────┴──────────┴───────────────────────┘ 双精度 double（64位）： ┌──────┬───────────┬────────────────────────────────────┐ │ 1位 │ 11位 │ 52位 │ │ s │ exp │ frac │ │符号位│ 指数域 │ 尾数域 │ └──────┴───────────┴────────────────────────────────────┘ ``` ### **5.3 三种情况** #### **规格化值（Normalized）** **条件**：exp ≠ 000...0 且 exp ≠ 111...1 ``` E = exp - Bias（偏置值） Bias = 2^(k-1) - 1 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 ``` #### **非规格化值（Denormalized）** **条件**：exp = 000...0 ``` E = 1 - Bias（固定值） M = 0.frac（无隐含1） 用途： 1. 表示 0（frac = 0 时） 2. 表示非常接近 0 的数（渐进下溢） ``` ``` +0: 0 00000000 00000000000000000000000 -0: 1 00000000 00000000000000000000000 注意：+0 和 -0 在比较时相等 ``` #### **特殊值（Special）** **条件**：exp = 111...1 ``` 无穷大（Infinity）：frac = 0 +∞: 0 11111111 00000000000000000000000 -∞: 1 11111111 00000000000000000000000 产生情况：1.0/0.0、溢出 NaN（Not a Number）：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 默认使用**向偶数舍入（Round to Even）**： ``` 当恰好在中间时，舍入到最近的偶数 例（舍入到整数）： 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 ``` --- ## **六、位运算** ### **6.1 布尔代数基础** > *💡 布尔代数起源于1850年前后乔治·布尔（George Boole）的工作，将逻辑真/假映射到二进制1/0。* C语言支持按位进行布尔运算： - `&` 按位与 - `|` 按位或 - `~` 按位取反 - `^` 按位异或 - `<<` 左移 - `>>` 右移 ### **6.2 布尔位运算** #### **位与（AND）**`&` **规则：同真为真，其余为假** | **A** | **B** | **A & B** | | --- | --- | --- | | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | **应用：** ``` x & 0x0F // 取低4位（掩码） x & 1 // 判断奇偶：0偶1奇 x & ~(1 << k) // 将第k位清零 x & (x-1) == 0 // 判断2的幂（且x≠0） x & (-x) // 取最低位的1（lowbit） ``` #### **位或（OR）**`|` **规则：同假为假，其余为真** | **A** | **B** | **A | B** | | --- | --- | --- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | **应用：** ``` x | (1 << k) // 将第k位置1 0x00FF | 0xFF00 // 合并位模式 flags | OPTION_A | OPTION_B // 添加多个选项 ``` #### **异或（XOR）**`^` **规则：相同为0，不同为1** | **A** | **B** | **A ^ B** | | --- | --- | --- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | **重要性质：** - `x ^ 0 = x`（与0异或不变） - `x ^ x = 0`（与自身异或为0） - `x ^ y ^ y = x`（异或两次还原） **应用：** ``` // 不用临时变量交换两数 a ^= b; b ^= a; a ^= b; // 判断相等 !(x ^ y) // x==y 时返回1 // 翻转特定位 x ^ (1 << k) // 找出只出现一次的数（其他都出现两次） int result = 0; for (int i = 0; i < n; i++) result ^= nums[i]; // 简单加密 encrypted = data ^ key; decrypted = encrypted ^ key; // 还原 ``` #### **按位取反（NOT）**`~` **规则：0变1，1变0** ``` ~0x00 = 0xFF // (以8位为例) ~0x0F = 0xF0 ``` > *注意：对于有符号数，*`~x = -(x+1)`*（补码性质）* ### **6.3 移位运算** #### **左移** `<<` 将二进制位整体左移，**右边补0**： ``` x << k // 相当于 x × 2^k（不溢出时） 5 << 2 // 0101 → 010100 = 20 = 5×4 1 << n // 2的n次幂 ``` #### **右移** `>>` 将二进制位整体右移： | **类型** | **填充方式** | **名称** | | --- | --- | --- | | 无符号数 | 左边补 **0** | 逻辑右移 | | 有符号数 | 左边补 **符号位** | 算术右移 | ``` // 无符号数 unsigned u = 0xF0; // 11110000 u >> 4 // 00001111 = 0x0F // 有符号数 int n = -8; // 11111000 (8位补码) n >> 2 // 11111110 = -2 x >> k // 相当于 x ÷ 2^k（向下取整） ``` #### **移位注意事项** ``` // ❌ 错误：移位量为负数或超过位宽（未定义行为） x << -2 // 未定义 x << 32 // 对于32位int未定义 // ⚠️ 优先级：加减 > 移位 1 << 2 + 3 << 4 // 实际是 1 << (2+3) << 4 (1 << 2) + (3 << 4) // 这才是想要的：4 + 48 = 52 // ⚠️ 结合性：左结合 x << j << k // 等价于 (x << j) << k ``` **Java 的明确定义：** ``` x >> k // 算术右移 x >>> k // 逻辑右移（Java特有） ``` ### **6.4 逻辑运算 vs 位运算** | | **位运算** | **逻辑运算** | | --- | --- | --- | | 运算符 | `&` `|` `~` `^` | `&&` `||` `!` | | 操作对象 | 每一个二进制位 | 整个值（非0视为真） | | 返回值 | 位运算结果 | 0 或 1 | | 短路求值 | ❌ 无 | ✅ 有 | ``` 5 & 4 // 0101 & 0100 = 0100 = 4 5 && 4 // true && true = 1 5 | 4 // 0101 | 0100 = 0101 = 5 5 || 4 // true || true = 1 ~4 // ...11111011 = -5（补码） !4 // !true = 0 ``` **短路求值的应用：** ``` // 逻辑运算会短路 1 || anything // 直接返回1，不计算anything 0 && anything // 直接返回0，不计算anything // 常见安全写法 if (p != NULL && *p == value) // p为NULL时不会访问*p ``` **用位运算实现判断相等：** ``` !(x ^ y) // x==y 时返回1，否则返回0 ``` ### **6.5 位运算技巧汇总** | **操作** | **表达式** | **说明** | | --- | --- | --- | | 获取第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;` | | | 取绝对值(32位) | `(x^(x>>31))-(x>>31)` | 无分支 | | 统计1的个数 | 见下方代码 | Brian Kernighan算法 | **统计1的个数：** ``` int count = 0; while (x) { x &= (x - 1); // 清除最低位的1 count++; } ``` **位域操作：** ``` // 提取位域 [high:low]（包含两端） (x >> low) & ((1 << (high - low + 1)) - 1) // 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)) ``` --- ## **七、可移植性与最佳实践** ### **7.1 固定宽度类型** 使用 `` 中的类型确保跨平台一致性： ``` int8_t / uint8_t // 精确 8 位 int16_t / uint16_t // 精确 16 位 int32_t / uint32_t // 精确 32 位 int64_t / uint64_t // 精确 64 位 size_t // 无符号，足够存储任何对象大小 ptrdiff_t // 有符号，足够存储指针差值 ``` ### **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` | 使用括号明确优先级 | ### **7.3 调试工具** **打印二进制：** ``` void print_binary(unsigned n) { for (int i = 31; i >= 0; i--) { printf("%d", (n >> i) & 1); if (i % 8 == 0) printf(" "); } printf("\n"); } ``` **打印浮点数位模式：** ``` void print_float_bits(float f) { unsigned u = *(unsigned*)&f; printf("符号: %d\n", (u >> 31) & 1); printf("指数: %d (实际: %d)\n", (u >> 23) & 0xFF, ((u >> 23) & 0xFF) - 127); printf("尾数: 0x%06X\n", u & 0x7FFFFF); } ``` --- ## **八、知识图谱与总结** ``` 计算机信息表示 │ ├── 信息存储基础 │ ├── 位、字节、字 │ ├── 进制系统 │ │ ├── 二进制（计算机内部） │ │ ├── 八进制（3位二进制） │ │ ├── 十进制（人类习惯） │ │ └── 十六进制（4位二进制） │ ├── 进制转换 │ │ ├── 反复除法（D→其他） │ │ ├── 按权展开（其他→D） │ │ └── 直接转换（B↔O↔H） │ └── 字节顺序（大端/小端） │ ├── 整数表示 │ ├── 无符号编码（直接二进制） │ ├── 有符号编码 │ │ ├── 原码（符号位+绝对值） │ │ ├── 反码（负数取反） │ │ └── 补码（反码+1）★现代使用 │ ├── 有无符号转换 │ └── 取值范围与溢出 │ ├── 整数运算 │ ├── 加法与溢出检测 │ ├── 取负（~x + 1） │ └── 乘除法（移位优化） │ ├── 浮点数表示（IEEE 754） │ ├── 格式：符号位 + 指数域 + 尾数域 │ ├── 规格化数（正常情况） │ ├── 非规格化数（接近零） │ ├── 特殊值（∞, NaN） │ ├── 舍入规则（向偶数舍入） │ └── 运算特性（不满足结合律） │ └── 位运算 ├── 布尔位运算 │ ├── 与 &（同真为真） │ ├── 或 |（同假为假） │ ├── 异或 ^（不同为真） │ └── 取反 ~ ├── 移位运算 │ ├── 左移 <<（×2^k） │ └── 右移 >>（÷2^k，注意符号） ├── 逻辑运算 vs 位运算 └── 实用技巧（掩码、清位、置位...） ``` --- ## **参考资料** - 《深入理解计算机系统》(CSAPP) 第2章 - IEEE 754-2019 浮点数标准 - 《Hacker's Delight》位运算技巧