第二课：数据表示与计算

一、进制——计算机的数学基石

1.1、人类计数方法的演进历程

1.1.1 手指计数：十进制的生物学起源

核心原理：人类双手共10根手指 → 最自然的计数工具
考古证据：

• 古埃及象形数字：𓏤(1)、𓎆(10)、𓍢(100) → 10倍递增
• 汉语数字："十"字即双手交叉象形
• 拉丁语数字：digit(手指/数字)同源

数学表达：
$N = d_n \times 10^n + ... + d_1 \times 10^1 + d_0 \times 10^0$
（$d_i$ 取值 0-9）

1.1.2. 其他进制的历史实践

进制	文明	应用场景	现代遗存
5进制	玛雅/凯尔特	单手计数	罗马数字Ⅴ=5
12进制	苏美尔	天文历法(12月/12时辰)	时钟/打(12个)
20进制	玛雅/阿兹特克	手脚并用(20指趾)	法语80=4×20(quatre-vingts)
60进制	巴比伦	角度/时间(60秒/分)	全球时间系统

1.1.3. 位值制革命：印度-阿拉伯数字

关键突破：

• 数字位置决定其权重（如 123 中 1 表示 100）
• 引入 0 作为占位符（公元628年 婆罗摩笈多）

罗马数字：CXXIII = 123 → 无位值概念
阿拉伯数字：123 = 1×100 + 2×10 + 3×1 → 位值制

1.2 计算机选择二进制的必然性

1.2.1 电子电路的物理本质

技术实现对比：

进制	状态数量	电路稳定性	误差容限	实现成本
二进制	2	★★★★★	极高	极低
十进制	10	★☆☆☆☆	极低	极高
三进制	3	★★☆☆☆	中等	高

关键实验：
1940年代贝尔实验室尝试十进制计算机
→ 需要10种稳定电压状态(0.5V,1.5V,...,4.5V)
→ 电压波动±0.2V即导致"3"和"4"混淆
→ 项目失败

1.2.2 布尔代数的完美契合

1854年乔治·布尔提出逻辑代数：
$X \land Y$ (与) → 串联开关
$X \lor Y$ (或) → 并联开关
$\neg X$ (非) → 反向器

电路实现：

二进制加法器：
A ⊕ B = (¬A∧B)∨(A∧¬B)  → 异或门
进位 = A∧B              → 与门

1.3 历史交汇点：从人脑到电脑

1.3.1 莱布尼茨的东方启示

1703年莱布尼茨发表《二进制算术阐释》：

• 受《易经》阴阳思想启发(0=阴,1=阳)
• "这是最完美的逻辑系统，一切数可归结为0和1"

历史启示：
人类选择十进制是生物进化的偶然结果
计算机选择二进制是物理规律的必然选择
这种差异恰恰体现了人类智慧——创造与自然规律协作的工具>

二、进制转换

2.1 十进制与其它进制互转的三种核心方法

2.1.1 除基取余法（十进制→其他进制）

数学原理：
整数可表示为多项式：
$N = d_n \times b^n + d_{n-1} \times b^{n-1} + \cdots + d_1 \times b^1 + d_0 \times b^0$

根据多项式的定义，将整数转换成 b 进制时，将整数除以2，并记录商和余数，余数即为 $d_i$ 。

• 每次除法实质是分离当前最低位
• 逆序操作重建了数字的位权结构
• 类似不断剥离数字的"外壳"

• 这个可以列数学多项式推导

// 整数转换C++实现
string intToBase(int n, int base) {
    if (n == 0) return "0";
    string digits = "0123456789ABCDEF";
    string result = "";
    while (n > 0) {
        result = digits[n % base] + result; // 余数逆序添加
        n /= base;
    }
    return result;
}

示例： 将 13 转换为二进制

结果： 10101101₂ (从下往上读余数)

2.1.2 乘基取整法（十进制小数→其他进制）

小数可表示为多项式：
$F = d_{-1} \times b^{-1} + d_{-2} \times b^{-2} + \cdots + d_{-m} \times b^{-m}$

转换过程：

1. 乘以基数 $b$ 得到整数和小数部分： $F × b = I_1 + F_1 \quad (0 ≤ F_1 < 1)$
2. 整数 $I_1$ 即是小数点后第一位
3. 对小数部分 $F_1$ 重复上述过程： $F_1 × b = I_2 + F_2$
4. 直到小数部分为0或达到精度，整数序列 $I_1I_2...I_m$ 即为结果

示例： 将 0.6875 转换为二进制

0.6875 × 2 = 1.375 → 取 1，余 0.375
0.375  × 2 = 0.75  → 取 0，余 0.75
0.75   × 2 = 1.5   → 取 1，余 0.5
0.5    × 2 = 1.0   → 取 1，余 0.0

结果： 0.1011₂ (从上往下读整数) `

* 小数精度控制` 问题： 0.3₁₀ 转二进制时无限循环

0.3×2=0.6 → 0
0.6×2=1.2 → 1
0.2×2=0.4 → 0
0.4×2=0.8 → 0
0.8×2=1.6 → 1 （开始循环）

解决方案： 指定精度（如保留8位） 结果：0.01001100₂（近似值）

string fracToBase(double f, int base, int precision) {
    string digits = "0123456789ABCDEF";
    string result = ".";
    for (int i = 0; i < precision && f > 0; i++) {
        f *= base;
        int digit = (int)f; // 取整数部分
        result += digits[digit];
        f -= digit; // 保留小数部分
    }
    return result;
}

2.1.3 位权展开法（其他进制→十进制）

公式： $N = d_{n-1} \times b^{n-1} + ... + d_0 \times b^0 + d_{-1} \times b^{-1} + ...$

示例： 将 3A.2C₁₆ 转换为十进制

3A.2C₁₆ = 3×16¹ + 10×16⁰ + 2×16⁻¹ + 12×16⁻²
        = 3×16 + 10×1 + 2/16 + 12/256
        = 48 + 10 + 0.125 + 0.046875
        = 58.171875₁₀

2.2 二进制 ↔ 八/十六进制快速转换

2.2.1 分组转换原理

2.2.2 转换表（核心工具）

二进制	八进制	十六进制	十进制
0000	0	0	0
0001	1	1	1
0010	2	2	2
0011	3	3	3
0100	4	4	4
0101	5	5	5
0110	6	6	6
0111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	A	10
1011	13	B	11
1100	14	C	12
1101	15	D	13
1110	16	E	14
1111	17	F	15

2.2.3 实战示例

1. 二进制 → 八进制： 11010110.01101₂

分组（补0）：
011 010 110 . 011 010
 3   2   6  .  3   2

结果：326.32₈

2. 十六进制 → 二进制： D5F.8A₁₆

D → 1101
5 → 0101
F → 1111
8 → 1000
A → 1010

结果：110101011111.10001010₂

2.3 特殊进制转换技巧

2.3.1 二进制 ↔ 十进制快速心算

二进制 → 十进制： 记住2的幂次表

2¹⁰=1024, 2⁹=512, 2⁸=256, 2⁷=128, 2⁶=64
2⁵=32, 2⁴=16, 2³=8, 2²=4, 2¹=2, 2⁰=1

示例：101101₁₂ = 32+8+4+1 = 45₁₀

十进制 → 二进制： 减权定位法

45-32=13 → 32位为1
13-8=5   → 8位为1
5-4=1    → 4位为1
1-1=0    → 1位为1
其余位为0 → 101101₂

2.3.2 负整数的进制转换

步骤：

1. 取绝对值转换(原码)
2. 求补码
3. 结果即为负数的二进制表示

示例： -45₁₀ 转8位二进制

1. 45₁₀ = 00101101₂
2. 取反：11010010
3. 加1：11010011₂

2.4 综合转换练习

进制/编码联动转换器

支持多种进制和编码的实时转换。修改任意输入框，该行其他值会自动更新。

选择显示的列：

八进制十六进制二进制补码移码浮点数编码

十进制	十六进制	二进制

使用说明：

• 修改任意输入框的值，该行的其他值会自动更新
• 当前正在编辑的输入框会以红色边框高亮显示
• 使用上方的复选框选择要显示的列，以优化显示空间
• 所有二进制编码显示为32位，并以4位一组格式显示
• 浮点数编码：
  • 默认显示彩色编码（符号位 |指数位 |尾数位）
  • 点击编码可切换到编辑模式
  • 按Enter或点击外部完成编辑

IEEE 754单精度浮点数标准：

单精度浮点数使用32位表示：

• 符号位 (1位)
• 指数位 (8位)
• 尾数位 (23位)

其值计算公式为：(-1)sign × (1 + mantissa) × 2(exponent - 127)

2.4.1 实战题目

1. 将 247.625₁₀ 转换为：

   • 二进制（保留8位小数）
   • 八进制
   • 十六进制

2. 将 3E7.A8₁₆ 转换为：

   • 二进制
   • 八进制
   • 十进制（保留3位小数）

3. 计算：1011₂ + 34₈ - 1B₁₆ = ？₁₀

2.4.2 答案验证

1. 247.625₁₀：

   • 二进制：11110111.1010₂
   • 八进制：367.5₈
   • 十六进制：F7.A₁₆

2. 3E7.A8₁₆：

   • 二进制：001111100111.10101000₂
   • 八进制：1747.52₈
   • 十进制：999.65625₁₀

3. 1011₂ + 34₈ - 1B₁₆： = 11₁₀ + 28₁₀ - 27₁₀ = 12₁₀

2.5 进制转换要点总结

转换类型	关键方法	注意事项
十进制→其他	整数：除基取余；小数：乘基取整	小数部分可能无限循环
其他→十进制	位权展开求和	注意小数点的位置
二进制↔八进制	3位分组转换	不足位补0
二进制↔十六进制	4位分组转换	区分大小写
负整数转换	补码表示	固定位数下进行
精度控制	指定保留位数	最后一位四舍五入

---

三、机器码——计算机如何理解负数**

3.1 原码：最直观的表示

定义：最高位为符号位（0正1负），其余为真值
例：+5 = 0 0000101， -5 = 1 0000101
致命缺陷：

1. ±0 问题：[+0]=0 0000000, [-0]=1 0000000 → 浪费编码
2. 加法错误：5 + (-5) = 0 0000101 + 1 0000101 = 1 0001010 = -10 ❌

3.2 反码：解决±0的过渡方案

规则：负数符号位不变，真值部分取反
例：-5 → 1 1111010
遗留问题：

• 循环进位复杂：5 + (-5) = 0 0000101 + 1 1111010 = 1 1111111 → -0
• 仍存在 -0 = 1 1111111

3.3 补码：计算机的终极方案

设计灵感：时钟校准（12小时制中，-3 ≡ +9）
数学原理：$x_{补} = 2^n + x$ （$n$为位数，$x<0$）
转换规则：

关键优势：

1. 统一加减法：A - B = A + (-B)补
2. 消除±0：0 唯一编码 00000000
3. 扩展范围：8位补码范围 -128 (10000000) ~ +127 (01111111)

3.4 补码计算减法

在二进制补码系统中，减法是通过加法实现的，核心原理是：
A - B = A + (-B)

其中 -B 是 B 的补码的相反数（即对 B 的补码取反再加 1）。以下是详细步骤和示例：

3.5 8位补码示例：计算 25 - 64

步骤 1：求各数的补码

十进制	二进制真值	补码
25	00011001	00011001
64	01000000	01000000

步骤 2：求 -64 的补码

• 对 64 的补码 01000000 取反：10111111
• 加 1：10111111 + 1 = 11000000

步骤 3：计算 25 + (-64)

  00011001  (25的补码)
+ 11000000  (-64的补码)
------------
  11011001  (结果补码)

• 高位进位：第 9 位产生进位 1 → 直接舍弃

步骤 4：验证结果

• 结果 11011001 是补码，转换为十进制：
  • 符号位为 1 → 负数
  • 数值部分取反加 1：1011001 → 取反 0100110 → 加 1 0100111 = 39
  • 结果为 -39
• 数学验证：25 - 64 = -39 ✓

---

关键原理剖析

为什么舍弃进位？

• 补码运算是 模 2ⁿ 运算（n 为位数）
• 8 位系统模 = 2⁸ = 256，溢出值相当于 256 的倍数，舍弃后不影响剩余部分的值：

  25 + (-64) = -39
  -39 + 256 = 217 → 二进制 11011001
  实际存储 11011001 等价于 -39（模 256 下）

补码减法统一性

---

3.6 常见陷阱与验证

1. 负数补码转换：

   • -B 的补码 ≠ B 的原码取反加 1，而是 对 B 的补码操作。

2. 溢出判断：

   • 若 A 和 -B 符号相同，但结果符号与两者相反 → 溢出（结果无效）

3. 快速验证工具：

   操作	二进制	十进制
   A (25)	00011001	25
   -B (-64)	11000000	-64
   A + (-B)	11011001	-39

编程应用：CPU 的 ALU 中，减法器实际由加法器和取反电路实现，效率极高。

3.7 移码：浮点数阶码的卫士

诞生原因：浮点数比较阶码大小时，补码需符号位参与 → 硬件复杂
定义：$x_{移} = x + 2^{n-1}$ （偏移$2^{n-1}$）
效果：将负数转换为正数，保留大小顺序
例（8位移码）：

真值	补码	移码（偏移128）
-128	10000000	00000000
0	00000000	10000000
+127	01111111	11111111

---

3.8 关键总结与陷阱提示

1. 进制转换：小数转换易丢精度，需指定保留位数
2. 补码原理：10000000 是特殊值（-128），无原码
3. 移码本质：补码的符号位取反（验证：0的移码=10000000）
4. 实战技巧：
   • 快速求 -5 补码：5 = 00000101 → 取反 11111010 → +1 = 11111011
   • 补码转真值：10101010 → 取反 11010101 → +1 = 11010110 = -86

附：8位机器码对比表

真值	原码	反码	补码	移码（128）
-128	无法表示	无法表示	10000000	00000000
-5	10000101	11111010	11111011	01111011
0	00000000	00000000	00000000	10000000
+5	00000101	00000101	00000101	10000101

---

2.4 补码转换技巧

• 求负数补码：绝对值原码 → 取反 → +1
• 补码转真值：符号位为1时，数值位取反+1，再加负号

四、浮点数表示（IEEE 754标准）

4.1 核心设计思想：科学计数法

公式：
$\text{值} = (-1)^{\text{符号}} \times \text{尾数} \times 2^{\text{指数}}$

单精度(32位)结构

各字段详解：

1. 符号位(Sign)

   • 0表示正数
   • 1表示负数

2. 指数域(Exponent)

   • 使用移码表示（偏移值127）
   • 实际指数 = 指数域值 - 127
   • 范围：-126到127

3. 尾数域(Fraction)

   • 隐含最高位1（规格化数）
   • 实际尾数 = 1 + 尾数域值
   • 23位提供约7位十进制精度

浮点数分类

类型	指数域	尾数域	数值表示
规格化数	1-254	任意	$(-1)^S \times (1.F) \times 2^{E-127}$
非规格化数	0	≠0	$(-1)^S \times (0.F) \times 2^{-126}$
零	0	0	$\pm 0$
无穷大	255	0	$\pm \infty$
NaN	255	≠0	非数字

4.2 浮点数转换实战

示例：将-37.625转换为IEEE 754单精度格式

步骤1：转换整数部分

$37_{10} = 100101_2$

步骤2：转换小数部分

$0.625_{10} = 0.101_2$
计算过程：

0.625 × 2 = 1.25 → 取1
0.25 × 2 = 0.5   → 取0
0.5 × 2 = 1.0    → 取1

步骤3：合并并规格化

$-37.625 = -100101.101_2$
规格化：$-1.00101101_2 \times 2^5$

步骤4：确定各字段值

1. 符号位：1（负数）
2. 指数域：实际指数5 → 移码 = 5 + 127 = 132 → $10000100_2$，阶符为0，阶码为$10000100_2$
3. 尾数域：$00101101$（隐含最高位1，只存储小数部分）

步骤5：组合结果

1 10000100 00101101000000000000000

十六进制：C2168000

浮点数的精度限制

浮点数类型	尾数位数	十进制精度
单精度(32位)	23位	约6-9位
双精度(64位)	52位	约15-17位
四精度(128位)	112位	约33-36位

五、位运算

5.1 位运算基础

1. 二进制表示

• 所有数据在计算机中以二进制存储（0/1）
• 示例：13 → 1101（8+4+0+1）

2. 位运算符表

运算符	名称	示例	说明
&	与	a & b	同1为1，否则为0
|	或	a | b	有1为1，同0为0
^	异或	a ^ b	相同为0，不同为1
~	取反	~a	0变1，1变0（按位取反）
<<	左移	a << k	二进制整体左移k位，低位补0
>>	右移	a >> k	二进制整体右移k位，高位补符号位

5.2 位运算实战技巧

1. 基本操作

int a = 13; // 1101  
int b = 6;  // 0110  

cout << (a & b)  << endl; // 0100 → 4  
cout << (a | b)  << endl; // 1111 → 15  
cout << (a ^ b)  << endl; // 1011 → 11  
cout << (~a)     << endl; // 0010（取反结果与位数有关，实际为补码）  
cout << (a << 2) << endl; // 110100 → 52  
cout << (a >> 2) << endl; // 0011 → 3  

2. 常用技巧

// 1. 判断奇偶  
bool isOdd(int x) {  
    return x & 1; // 奇数返回1，偶数返回0  
}  

// 2. 交换两个数（无需临时变量）  
void swap(int &a, int &b) {  
    a ^= b;  
    b ^= a;  
    a ^= b;  
}  

// 3. 获取最低位的1  
int lowbit(int x) {  
    return x & (-x); // 例如：x=12(1100), 返回4(100)  
}  

// 4. 检查第k位是否为1（从0开始计数）  
bool checkBit(int x, int k) {  
    return (x >> k) & 1; // 右移k位后与1  
}  

// 5. 将第k位设为1  
int setBit(int x, int k) {  
    return x | (1 << k);  
}  

// 6. 将第k位设为0  
int clearBit(int x, int k) {  
    return x & ~(1 << k);  
}  

5.3 位运算应用场景

1. 状态压缩

• 用整数二进制位表示状态（如子集、开关状态）

// 枚举n个元素的子集  
for (int mask = 0; mask < (1 << n); mask++) {  
    for (int i = 0; i < n; i++) {  
        if (mask & (1 << i)) {  
            // 第i个元素在子集中  
        }  
    }  
}  

2. 高效计算

• 乘法模拟：a << k 等价于 $a \times 2^k$
• 除法模拟：a >> k 等价于 $a \div 2^k$（向下取整）

3. 算法优化

• 布隆过滤器（Bloom Filter）
• 位图法（Bitmap）
• 动态规划状态压缩（如旅行商问题）

5.4 典型例题分析

题目1：二进制中1的个数

int countOnes(int x) {  
    int cnt = 0;  
    while (x) {  
        x &= (x - 1); // 每次消去最低位的1  
        cnt++;  
    }  
    return cnt;  
}  

题目2：只出现一次的数字（LeetCode 136）

int singleNumber(vector<int>& nums) {  
    int ans = 0;  
    for (int num : nums) ans ^= num; // 异或的消去律  
    return ans;  
}  

题目3：子集枚举（CSP-J常见题型）

vector<vector<int>> subsets(vector<int>& nums) {  
    vector<vector<int>> res;  
    int n = nums.size();  
    for (int mask = 0; mask < (1 << n); mask++) {  
        vector<int> subset;  
        for (int i = 0; i < n; i++) {  
            if (mask & (1 << i)) subset.push_back(nums[i]);  
        }  
        res.push_back(subset);  
    }  
    return res;  
}  

5.5 注意事项

1. 优先级问题：位运算优先级低于算术运算，建议加括号

   (a + b) >> 1  // 正确：先加再右移  
   a + b >> 1    // 错误：先右移再加  
2. 负数右移：高位补符号位（多数编译器），避免对负数使用
3. 防溢出：左移可能导致溢出，如 1 << 31 对 int 溢出

---

课后练习

1. 用位运算实现快速幂（计算 ( a^b % p )）
2. 反转一个整数的二进制位（LeetCode 190）
3. 用位运算判断两个数是否异号

掌握位运算可显著提升代码效率，尤其在竞赛中处理大量数据时效果显著。多加练习，理解其底层原理！