02 · 位、字节与整数

来源：第 2 讲 pp.3～68；小班第 2 讲；教材 §2.1～2.3。以下公式中的 w 是位宽，所有“模运算”都明确指无符号或固定位向量模型。

进制、字长与存储单位#

一个十六进制位恰好对应 4 个二进制位。十六进制便于压缩表示位串且保持位边界，十进制便于人的数量理解。0xDA = 11011010₂ = 218；8 位补码解释则是 218-256=-38。

C 只保证 sizeof(char)==1，一个 C 字节的位数由 CHAR_BIT 指定；本课假设 8 位字节。机器字长、C 的 int、汇编 word 不是同一概念：x86 的 word 是 16 位，quadword 是 64 位。KiB、MiB、GiB 严格对应 2¹⁰、2²⁰、2³⁰ 字节；KB/MB/GB 应看题设和厂商约定。

大小端与字符#

数值 0x1234ABCD 存在地址 p 开始的 4 个字节：

小端的“低”指低有效字节放低地址，不是把字节内部的比特反过来。x86 是小端。字符串按字符次序逐字节存储，不应整体翻转。字符串 "12" 占 3 字节：31、32、00。指针本身也是对象，其字节表示与它指向的内容不同。

网络字节序通常指多字节整数的大端表示。协议实现用 htons/htonl/ntohs/ntohl 等在约定边界转换；网卡不会自动替任意应用层结构体识别并修正全部字段。

可用 unsigned char * 检视对象字节；sizeof 返回 size_t，打印用 %zu。用不同类型指针直接解引用重解释对象可能触及别名或对齐规则，可靠的位复制可用 memcpy。

布尔代数与位向量#

逐位 & | ^ ~ 分别为交、并、异或、补。集合可以用位图表示：第 i 位为 1 表示元素 i 属于集合。x^x=0，x&~x=0，x|~x 是全 1；德摩根律为 ~(x&y)=~x|~y、~(x|y)=~x&~y。

&& || ! 判断零/非零，结果为 int 类型的 0 或 1，并且 &&、|| 从左到右短路。0xF0 & 0x0F=0，但 0xF0 && 0x0F=1。p && *p 在 p 为空时跳过解引用，但不能防止 p 是悬空或其他无效指针。

常用无符号位操作：

/* 前提：0 <= k < 32 */
x & (1u << k)       /* 测试第 k 位 */
x | (1u << k)       /* 置位 */
x & ~(1u << k)      /* 清位 */
x ^ (1u << k)       /* 翻转 */
x & (x - 1u)       /* 清掉最低的 1；x=0 时仍为 0 */
x & (0u - x)       /* 提取最低的 1 */

对 unsigned char 做运算时先发生整数提升；例如 ~(unsigned char)0 的表达式通常是 int 的 -1，而不是 255。需要取低 8 位时再转换或加掩码。

移位#

逻辑右移补 0；算术右移补原符号位；左移低位补 0，越出位宽的高位丢弃（位向量模型）。对位串 10110100 右移 2 位：逻辑结果 00101101，算术结果 11101101。

• C 无符号右移等价于向下取整除以 2ᵏ。
• 本课程 x86/GCC 模型中负有符号数右移是算术右移：-13 >> 2 为 -4；-13 / 4 向零截断为 -3。
• C 中移位数为负或不小于提升后左操作数位宽是未定义行为；不能把 x86 对移位计数的硬件掩码当成 C 规则。
• C 有符号左移的条件比无符号更严格；做掩码优先用无符号。1 << 31 与 1u << 31 的语言含义不同。
• 加减优先级高于移位：x + y << 2 解析为 (x+y)<<2。比较、位运算混用时显式加括号，例如 (x & mask) == 0。

无符号、原码、反码与补码#

对于位向量 x[w-1]...x[0]：

B2U(x) = Σ x[i]·2^i                        (i=0...w-1)
B2T(x) = -x[w-1]·2^(w-1) + Σ x[i]·2^i      (i=0...w-2)
UMax = 2^w-1
TMin = -2^(w-1)         TMax = 2^(w-1)-1

32 位边界：TMin=-2147483648（0x80000000），TMax=2147483647（0x7FFFFFFF），UMax=4294967295（0xFFFFFFFF）。补码的负数比正数多一个，只有一个零。

原码是符号位加绝对值；反码的负值编码由相应正值编码逐位取反获得；二者都有正零和负零。补码用模 2ʷ 的表示统一加减法，避免双零。w 位模型的取负是 ~x+1 (mod 2^w)；该位级恒等式对 TMin 也成立，结果位串仍为 TMin。数学上的 -TMin 超出同位宽有符号范围，C 的该取负会溢出，二者须分开。

类型转换、扩展、截断#

同位宽有符号→无符号：非负值不变，负值 x 映射到 x+2ʷ。反向按本课补码实现，若 u> TMax 则解释为 u-2ʷ。在 C 中，把不可表示无符号值转成有符号类型的具体规定应按所用标准和实现，不当作通用数学转换。

加宽：无符号零扩展；有符号符号扩展。例如 8 位 -12 为 F4，扩为 32 位是 FFFFFFF4。截断：只保留低 k 位，再按目标类型解释。加宽后再改成无符号时，应保持原值所要求的扩展，例如 short s=-1; unsigned u=s; 在本平台得到 0xFFFFFFFF，而不是 0x0000FFFF。

通常算术转换先做整数提升，再处理等级和可表示范围，不是只要出现 unsigned 就一律全变 unsigned：

十进制无后缀字面量与十六进制字面量的候选类型序列不同；-2147483648 是一元负号作用于正字面量，不应未经分析就认定正字面量已经是 int。用 <stdint.h> 固定宽度类型、INT_MIN 等宏有助于明确题设。

加、减、乘与溢出#

无符号加法是 (x+y) mod 2^w；判断溢出可比较结果是否小于任一操作数，或在运算前判断 x > UMax-y。补码硬件加法也保留低 w 位：两个同号数相加得到异号结果才是有符号溢出。异号相加不会有符号溢出。

8 位例子：250+10 的低位结果是 4（无符号进位）；100+60 的低位 0xA0 解释为 -96（正溢出）；-100-60 的低位 0x60 解释为 96（负溢出）。CF 与 OF 可以不同。

无符号减法也按模 2ʷ 运算；硬件 CF 表示借位。补码减法 a-b 的溢出条件：a、b 异号且结果符号不同于 a。乘法完整积可能需要 2w 位；有符号与无符号乘法的低 w 位相同，高 w 位未必相同。C 中不能先做有符号溢出再用结果检验溢出，可先提升到足够宽类型或做边界比较。

在模 2ʷ 的位向量运算下，加法与乘法仍满足交换、结合和分配律；不能据此证明发生有符号溢出的 C 代码合法。判断恒等式时先写明讨论哪一种模型。

用移位替代常数乘除#

x*10 可分解为 (x<<3)+(x<<1)，x*15 可分解为 (x<<4)-x，但这只是位向量或满足语言范围约束时的等价关系。编译器会综合成本选 LEA、移位、加减或乘法，不是所有乘法都必须替换。

对于 0≤k<w，本课算术右移模型下，有符号除 2ᵏ 向零舍入可按负数加偏置实现：

x >= 0:  x >> k
x <  0: (x + (2^k - 1)) >> k

例：-13 除 4，先 -13+3=-10，再算术右移 2 位得到 -3。k=0 的偏置为 0。构造 2^k 的 C 代码时还要避免有符号移位本身越界。

完整算例与常见陷阱#

设 8 位 a=0xB5、b=0x5C：无符号 a=181，补码 a=-75；a&b=0x14，逻辑 !!b=1。将 short -12 扩为 int，位模式 FFFFFFF4；若问最低地址的字节，x86 小端答案 F4；若问最高有效字节，才是 FF。“首字节”不明确时必须说明解释。

无符号倒序循环 for (i=n-1; i>=0; i--) 不会靠 i>=0 结束，n=0 还会立即下溢。常用 for (size_t i=n; i>0; --i) use(i-1);。

自检与练习方向#

能从任意 w 位编码算出 B2U/B2T，并反向编码；能给出同位宽的 signed/unsigned 比较反例；能区分整数提升和截断；能解释负数除法的偏置；能写出同一对象的大端、小端字节序。教材作业：2.59（组合字节）、2.60（替换字节）、2.71（字节提取与符号扩展）。