位表示：同一串比特为什么会有不同含义

一个字节 11111111 可以解释成无符号数 255，也可以解释成 8 位补码的 −1。内存只保存位；类型、指令和程序约定决定怎样解释。理解这一点，才能分清“硬件算出来的低位结果”与“C 语言是否允许这样写”。

无符号与补码

n 位无符号数的权重都是正数，范围是 0 到 $2^n-1$；n 位补码把最高位权重改成 $-2^{n-1}$，范围是 $-2^{n-1}$ 到 $2^{n-1}-1$。8 位 10000101 因而是 −128 + 4 + 1 = −123。取反加一得到相反数的位模式，但最小补码数没有同宽的正数对应物。

例如，8 位补码 127 + 1 的低八位是 10000000。用这个模型解释机器溢出没有问题；在 C 中执行 int32_t x = INT32_MAX; x + 1 却是有符号溢出，属于未定义行为。编译器可以据“合法执行不溢出”进行优化。想做模 $2^{32}$ 运算，应明确使用 uint32_t；想检测有符号加法溢出，可先转成能容纳中间结果的 int64_t。

int64_t wide = (int64_t)a + b;
if (wide < INT32_MIN || wide > INT32_MAX) return false;
*out = (int32_t)wide;

转换必须发生在相加之前。(int64_t)(a + b) 无法挽救已经发生的溢出。这与内存申请时先做 n * sizeof(T) 再检查是同一类错误：检查要早于危险运算。

位操作如何组织

本仓库 bits.c 的 population 每次执行 value &= value - 1，消去最右侧一个 1。以 10110000 为例，减一变成 10101111，相与得到 10100000；循环次数等于 1 的数量。这是明确采用无符号模运算的算法，而不是依赖有符号溢出。

rotate_left 先把位数模 32，再单独处理零。表达式 (x << n) | (x >> (32-n)) 看似能直接处理所有 n，但 n=0 时右移 32 位不合法。C 对移位量要求小于左操作数提升后类型的位宽。另一个陷阱是 1 << 31：常量 1 通常是有符号 int；应使用 UINT32_C(1) 明确位宽和符号。

按位 & 与逻辑 && 也不同：前者逐位计算，后者把操作数解释成真或假，并短路求值。掩码 0xff 用来保留低字节，而布尔判断 x != 0 用来表示条件，不要互换。

字节序与浮点

0x12345678 在小端机器上由低地址到高地址存为 78 56 34 12。字节序不改变数值，也不改变 x >> 8 的数值语义；它改变多字节对象在内存里的排列。使用 memcpy 或 unsigned char * 观察对象表示，避免违反严格别名规则的指针强转。

IEEE 754 binary32 的字段为 1 位符号、8 位指数和 23 位小数。正规数的值是 $(-1{)}^s(1.f)2^{e-127}$。指数为零时使用非正规规则与零；指数全为一时区分无穷与 NaN。比如 1.5 的字段为符号 0、指数 127、小数最高位 1，对应 0x3fc00000。注意普通 C 的 float 并非由语言标准强制为 binary32；实验环境有明确假设，通用代码需核对实现。

浮点加法先对齐指数、相加、规格化、舍入，有限尾数意味着它不满足通常的结合律。对数量级差距很大的值，先加小数或后加小数可能得到不同结果。这会在并行归约和语言模型数值计算中再次出现。

运行与改写

make -C labs/csapp bits
./labs/csapp/bits

小端平台会显示 memory bytes: 78 56 34 12，无符号回绕输出为 0，最后显示 bits: boundary checks passed。端序输出允许因平台变化，其余判据不依赖端序。

练习顺序：先手算 population(0x80000001)；再实现 rotate_right 并覆盖 0、1、31、32、33；最后增加安全乘法函数，测试 INT32_MIN * -1。为每个函数保留普通可读的参考写法，用边界值和随机样本比较，不要先追求最少运算符。

/* Original exercises: defined C11 operations, not restricted Data Lab answers. */
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

static unsigned population(uint32_t value) {
    unsigned count = 0;
    while (value) {
        value &= value - UINT32_C(1);
        ++count;
    }
    return count;
}

static uint32_t rotate_left(uint32_t value, unsigned amount) {
    amount %= 32;
    if (amount == 0) return value; /* A shift by 32 would be undefined. */
    return (value << amount) | (value >> (32 - amount));
}

static bool add_i32(int32_t a, int32_t b, int32_t *out) {
    int64_t wide = (int64_t)a + b;
    if (wide < INT32_MIN || wide > INT32_MAX) return false;
    *out = (int32_t)wide;
    return true;
}

int main(void) {
    assert(CHAR_BIT == 8);
    assert(population(0) == 0);
    assert(population(UINT32_MAX) == 32);
    assert(population(UINT32_C(0x80000001)) == 2);
    assert(rotate_left(UINT32_C(0x80000001), 1) == 3);
    assert(rotate_left(UINT32_C(0x80000001), 0) == UINT32_C(0x80000001));
    assert(rotate_left(UINT32_C(0x80000001), 32) == UINT32_C(0x80000001));
    int32_t result = 99;
    assert(!add_i32(INT32_MAX, 1, &result) && result == 99);
    assert(!add_i32(INT32_MIN, -1, &result) && result == 99);
    assert(add_i32(INT32_MIN, INT32_MAX, &result) && result == -1);
    assert(add_i32(15, -7, &result) && result == 8);
    uint32_t word = UINT32_C(0x12345678);
    unsigned char bytes[sizeof word];
    memcpy(bytes, &word, sizeof bytes);
    printf("memory bytes: %02x %02x %02x %02x\n", bytes[0], bytes[1], bytes[2], bytes[3]);
    printf("wrap: %" PRIu32 "\n", UINT32_MAX + UINT32_C(1));
    puts("bits: boundary checks passed");
    return 0;
}

对应 Data Lab

官方 Data Lab 在 bits.c 的每个函数注释里规定可用操作与数量，整数题和浮点题的规则不同。先用 btest 检查函数行为，再用 dlc 检查规则，最后用 driver 查看综合结果。本站代码使用循环、固定宽度类型和更宽整数，是便于理解与验证的练习，不符合全部 Data Lab 的限制，也不应直接粘贴为实验答案。官方 Data Lab 说明

自测：为什么 `abs(INT32_MIN)` 不能用 int32_t 正确表示？

32 位补码有一个额外负数：−2147483648 的相反数是 2147483648，而最大正数为 2147483647。可以先提升为 int64_t 再取负，或返回无符号大小；直接在 int32_t 上取负会溢出。

自测：为什么测试 1000 个小正数仍可能遗漏严重错误？

错误通常集中在表示边界：零、全一、符号位、最大最小数、正负混合、移位量为零或字长。正常范围样本无法覆盖溢出、掩码和特殊字段路径。测试应依据表示类别划分，再补随机样本。

下一章：机器代码与栈。