第 3 讲 · 数据表示、位运算与内存

屏幕上的 200、0.3 和 'A' 看起来完全不同，进入计算机后却都要变成有限长度的 0 和 1。类型的作用，就是约定怎样解释这些比特。

1. 位、字节与内存

  • bit（位）是一个二进制位置，只能取 0 或 1；
  • byte（字节）通常由 8 位组成，是 C 中 sizeof 的计量单位；
  • 内存按字节编号，每个编号就是一个地址；
  • 一个多字节变量占据一段连续地址。
char c;
int n;
double x;

printf("%zu %zu %zu\n", sizeof c, sizeof n, sizeof x);

sizeof(char) 按定义永远是 1；这个“1”指一个 C 字节。其他类型的大小由实现决定。

2. 进制转换

2.1 任意进制转十进制

把每一位乘上对应的基数幂再求和。例如：

(10011)2=1×24+0×23+0×22+1×2+1=19.(10011)_2=1\times2^4+0\times2^3+0\times2^2+1\times2+1=19.

2.2 十进制整数转其他进制

反复“除以基数取余”，余数倒序排列：

19 ÷ 2 = 9 余 1
 9 ÷ 2 = 4 余 1
 4 ÷ 2 = 2 余 0
 2 ÷ 2 = 1 余 0
 1 ÷ 2 = 0 余 1

所以 19 = (10011)₂

2.3 二进制与八、十六进制

从右向左每 3 个二进制位对应 1 个八进制位，每 4 位对应 1 个十六进制位：

010 011₂ = 23₈
0001 0011₂ = 13₁₆

它们适合人阅读二进制模式。任意七进制等其他进制仍按“位权”和“除基取余”处理。

3. 有符号整数为什么用补码

设一个整数占 ww 位。无符号整数表示范围为：

0∼2w−1.0\sim 2^w-1.

常见补码有符号整数的范围为：

−2w−1∼2w−1−1.-2^{w-1}\sim 2^{w-1}-1.

3.1 原码、反码、补码

对正数，三者相同。对负数：

  1. 先写绝对值的二进制；
  2. 所有位取反得到反码；
  3. 反码加 1 得到补码。

以 8 位的 −7-7 为例：

 7 的原码：0000 0111
逐位取反：1111 1000
      加一：1111 1001  ← -7 的补码

补码把加减法统一成同一套二进制加法，并且只有一个 0。8 位补码中 1000 0000 表示 −128-128，因此负数一侧比正数多一个值。

3.2 截断与溢出

课件用下面的现象引出补码：

signed char sum = 100 + 100;
printf("%d\n", sum);

在 8 位 signed char 的常见实现中，200 的低 8 位为 1100 1000，按补码解释得到 -56。这里有两层风险：结果超出目标类型范围；从较宽整数转换为较窄有符号类型的结果还可能依实现而定。正确做法是选够宽的类型，而不是利用回绕猜结果。

4. 位运算

位运算直接作用于整数的每一位：

运算含义某一位的规则
a & b按位与两位都为 1 才为 1
a | b按位或至少一位为 1 就为 1
a ^ b按位异或两位不同为 1
~a按位取反0、1 互换
a << k左移整体向高位移动
a >> k右移整体向低位移动

逻辑运算 &&、|| 只关心整个操作数真假；位运算 &、| 会逐位计算，不能混用。

4.1 掩码的三个基本动作

假设从 0 开始编号第 k 位：

unsigned mask = 1u << k;

x |= mask;    /* 第 k 位置 1 */
x &= ~mask;   /* 第 k 位清 0 */
x ^= mask;    /* 第 k 位翻转 */

判断奇偶性就是检查最低位：

if ((x & 1u) != 0) {
    /* x 为奇数 */
}

取一段连续位可先构造低位全 1 的掩码：

unsigned low_11 = (1u << 11) - 1;
unsigned field = x & low_11;

4.2 左移和右移的边界

对无符号数，在结果可表示时左移 kk 位相当于乘 2k2^k，右移相当于整除 2k2^k。但需要注意：

  • 移动位数不能为负，也不能大于或等于类型位宽；
  • 无符号右移左侧补 0；
  • 负的有符号数右移结果由实现定义；
  • 有符号数左移溢出会产生未定义行为。

处理位模式时优先使用 unsigned 类型。

异或交换在课件中作为位运算例子出现：

a ^= b;
b ^= a;
a ^= b;

它要求两者不是同一对象，可读性也不如临时变量。工程代码应写普通交换，不必为了“少一个变量”牺牲清晰性。

5. 浮点数：范围和精度不能同时无限

十进制小数 0.6250.625 可以有限写成二进制：

0.625=(0.101)2.0.625=(0.101)_2.

而 0.30.3 的二进制展开无限循环，只能截取一个近似值。因此：

float y = 0.3f;
printf("%d\n", y == 0.3); /* 常见结果为 0 */

右侧 0.3 是 double，y 保存的是先舍入到 float 的近似值，再提升回 double，二者不一定相等。

5.1 IEEE 754 的直觉

常见的 float 和 double 使用 IEEE 754，把有限位宽分成：

符号位 | 指数 | 尾数

普通规格化数可理解为：

(−1)s×1.M2×2e.(-1)^s\times 1.M_2\times 2^e.

指数控制范围，尾数控制有效数字。数值绝对值越大，相邻可表示浮点数之间的绝对间隔也越大，这就是“小数点会浮动”的含义。

全 1 指数等特殊编码还能表示无穷和 NaN。NaN 与任何值比较都不相等，包括它自己；不能用普通相等判断识别它，应使用 <math.h> 中的分类函数。

5.2 误差比较

固定绝对误差适合数值量级已知的题：

#include <math.h>

const double eps = 1e-9;
if (fabs(a - b) < eps) {
    /* 近似相等 */
}

量级跨度很大时，结合相对误差更稳妥：

double scale = fmax(1.0, fmax(fabs(a), fabs(b)));
if (fabs(a - b) <= 1e-9 * scale) {
    /* 近似相等 */
}

machine epsilon 描述 1 与大于 1 的下一个可表示数之间的距离；它不是所有计算都应直接使用的统一容差。

5.3 求根时按情况分支

解 ax2+bx+c=0ax^2+bx+c=0 时，浮点版程序应先判断 aa 是否接近 0，再判断判别式：

double delta = b * b - 4 * a * c;
if (fabs(a) < eps) {
    /* 退化为一次方程 */
} else if (delta > eps) {
    /* 两个不同实根 */
} else if (fabs(delta) <= eps) {
    /* 重根 */
} else {
    /* 无实根 */
}

这比直接写 delta == 0 更符合浮点数实际表示方式。

6. 变量、地址与字节序

变量可以看成一段内存空间的名字，具有名称、类型、大小、值和地址：

int value = 0x12345678;
printf("value=%d, size=%zu, address=%p\n",
       value, sizeof value, (void *)&value);

多字节数据的字节排列有两种常见方式：

  • little-endian：低有效字节放低地址；
  • big-endian：高有效字节放低地址。

Intel/AMD 桌面处理器通常使用小端；网络协议常约定大端字节序。字节序只影响多字节对象在内存或传输中的排列，不改变 int 运算看到的数值。

7. 数组、sizeof 与存储位置

int data[5] = {1, 3, 5};

数组元素类型相同且连续存放，后两个元素初始化为 0。

size_t count = sizeof data / sizeof data[0];

这个写法只在 data 仍是数组的作用域内有效。把数组传给函数后，参数会按指针处理，sizeof 得不到原数组长度，所以长度应作为额外参数传入。

大型局部数组会占用有限的调用栈，可能导致栈溢出。全局/静态数组位于静态存储区，动态数组可从堆中申请。选择放在哪里应由容量和生命周期决定，而不是机械地“数组大就全局”。

课件还讨论了 C99 变长数组（VLA）：数组长度可以在运行时决定，但支持情况和栈容量有限，C++ 也没有标准 VLA。需要可控的大空间时，动态内存通常更通用。

8. 标准输入输出重定向

程序里的 stdin 和 stdout 默认连接键盘与控制台，也可以被重定向到文件。

8.1 在命令行重定向

./program < input.txt > output.txt

程序本身不需要修改，仍然从 stdin 读、向 stdout 写。

8.2 在程序中重定向

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

这适合本地调试，但提交 OJ 前通常应删除或用条件编译隔离，否则评测程序会找不到本地文件。

9. 本讲最重要的因果链

类型
  ├─ 决定占多少字节
  ├─ 决定同一串比特怎样解释
  ├─ 决定数值范围和精度
  └─ 决定表达式、转换和输入输出格式

当程序出现整数变负、浮点比较失败、格式化输入异常、位运算结果奇怪时，不要只盯着某一行语法；先沿这条因果链检查“数据到底以什么类型保存和计算”。

评论