Mdr-C-Tutorial

21.4 整数与位操作辅助函数 ​

在底层系统编程中，许多高频出现的整数与位运算需求看似代码量极小，例如为内存分配器寻找「大于等于 n 的最小 2 的整数次幂」、从跨平台网络报文中按大端或小端顺序拼接 32 位整数、或者在动态扩容数组前预测 n * size 乘积是否会越界溢出。这些核心算法往往只有寥寥十余行，但在编写时却极易触碰 C 语言标准中最幽深的未定义行为陷阱：移位位数大于等于对象类型的位宽、有符号整型在左移时发生数值溢出、或是宽度较窄的无符号整型（如 uint8_t、uint16_t）在参与运算前被编译器自动隐式提升为 int。

针对这些工程痛点，本节将严格遵循标准规格，从零构建一套高可靠的无符号整数与位操作辅助工具函数，并结合穷举比对、确定性慢速参照实现以及数学代数性质检查，全方位验证其正确性。相关代码紧随 21.1 范围、命名与契约 中搭建的工程组织方式，源码统一存放在 code/开发与工程基础/21_库接口实现练习/ 中。第一部分中完成的 mdr_popcount_u32 与 mdr_bswap32 将继续直接复用，而本节新增的扩展函数均集中维护在 include/mdr_bits.h 与 src/mdr_bits.c 中。

1. 无符号运算与移位规则 ​

为了从根本上规避有符号整数溢出带来的未定义行为，本节设计的所有位运算接口全部严格建立在固定宽度的无符号整型基础之上，具体选用 uint32_t、uint64_t 与标准的地址计量类型 size_t。在 ISO C 规范中，无符号整数算术遵循确定的模 2^N 进位回绕规则，例如 UINT32_MAX + 1u 的结果稳定回绕至 0，这一行为在所有合规的 C 编译器中均具备确切的语义保障。也正因如此，在判断无符号加法是否溢出时，绝不能通过观察相加后的数值是否发生突变来推断，而必须依靠操作数与极值上限之间的严格代数关系进行事前或事后校验。

然而，移位运算符 << 与 >> 的语义规则却严苛得多。C 标准明确裁定：移位的位数若小于 0，或者大于等于被移位对象类型本身的有效位宽，均属于未定义行为；若对有符号数执行左移且计算结果超出了该有符号类型所能容纳的数值极限，同样构成未定义行为。至于对有符号负数执行右移操作，在 C17 中属于由实现定义的行为（各大主流编译器如 GCC、Clang 与 MSVC 默认均生成算术右移指令以保留符号位），但为了保证绝对的跨平台一致性，本节的位操作接口坚决不对此类平台特性产生任何依赖。

除了移位规则之外，窄整型隐式提升（Integer Promotion）是另一个极易引发隐蔽逻辑缺陷的语言特性：在 C 语言的求值规则中，任何位宽小于 int 的整型对象（例如 uint8_t 与 uint16_t）一旦出现在表达式中，都会在运算执行前被预先提升为有符号的 int 类型（若 int 足以完整容纳其取值空间），且中间表达式的求值均在 int 精度下完成。这导致对一个 uint8_t 对象执行按位取反 ~ 时，计算得到的并不是 8 位的局部反码，而是一个高 24 位全部被置为 1 的 32 位有符号整数：

c
#include <stdint.h>
#include <stdio.h>

int main(void) {
    uint8_t byte = 0x0Fu;
    uint16_t word = 0xFFFFu;

    printf("~byte       = %08X\n", (unsigned)~byte);
    printf("byte << 4   = %08X\n", (unsigned)(byte << 4));
    printf("word * word = %08X\n", (unsigned)(word * word));
    printf("sizeof(byte + byte) = %zu\n", sizeof(byte + byte));
    return 0;
}
zsh - promo
text
$ gcc -std=c17 -Wall -Wextra promo.c -o promo
$ ./promo
~byte       = FFFFFFF0
byte << 4   = 000000F0
word * word = FFFE0001
sizeof(byte + byte) = 4

~byte 补出了高 24 位；word * word 的结果 0xFFFE0001 早就超出了 16 位，但因为它是在 int 里算的，没有回落到 16 位。如果把它存回 uint16_t，才会截断成 0x0001。Windows 上 MinGW-w64 GCC 13.2 与 Linux 上 GCC 14.2 的输出相同。

需要固定宽度的位运算时，先转换成 uint32_t 或 uint64_t 再算，别指望小类型保留自己的宽度。移位量也一样：x << k 里的 k 先用 k &= 31 之类的手段压回范围内，或者让规格明确写出调用方要保证什么。

无符号算术与移位的规则

无符号整数的加、减、乘按 2^N 取模，结果总是有定义的。移位位数等于或大于类型宽度、负数移位、有符号左移溢出都属于未定义行为。uint8_t、uint16_t 参与算术或位运算前先提升为 int，结果的类型是 int。本节的函数一律在 uint32_t、uint64_t、size_t 上运算，移位量在函数内部压回范围。

移位位数越界时，程序不会在编译期报错，只在运行时给出奇怪的结果。同一份代码在 Linux 上用 UBSan 构建运行：

c
#include <stdint.h>
#include <stdio.h>

int main(void) {
    uint32_t x = 0x80000000u;

    printf("%u\n", (unsigned)(x << 32));
    return 0;
}
zsh - shift_demo
text
$ gcc -std=c17 -Wall -Wextra -fsanitize=undefined -fno-sanitize-recover=all shift_demo.c -o shift_demo
shift_demo.c: In function ‘main’:
shift_demo.c:7:33: warning: left shift count >= width of type [-Wshift-count-overflow]
    7 |     printf("%u\n", (unsigned)(x << 32));
      |                                 ^~
$ ./shift_demo
shift_demo.c:7:33: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
$ echo $?
1

-Wshift-count-overflow 在编译期就报了，UBSan 又给出一次带位置的运行时报告，程序以状态 1 退出。本机 MinGW-w64 GCC 13.2 没有 UBSan 运行库，同一份程序只能看到那条编译警告，运行输出 2147483648——这是编译器把移位次数按 32 取模的结果，同样不可依赖。移位次数不是编译期常量时，连那条警告都没有，只能靠 UBSan 或代码审查。

2. 前导零、尾随零与计数 ​

在构建位计数接口之前，必须首先从规格层面明确界定输入为 0 时的边界返回值。在 C23 官方标准库 <stdbit.h> 中，标准明确规定 stdc_leading_zeros 与 stdc_trailing_zeros 在接收到 0 时，统一返回当前整型对象的物理位宽。本库完全采纳这一现代化契约：mdr_clz_u32(0) 返回 32，mdr_clz_u64(0) 返回 64。这一规定的必要性在于：后续实现的有效位宽计算接口 mdr_bit_width_u32 深度依赖它来得出 0 的位宽为 0；若此处留下未定义漏洞，整个工具链的逻辑自洽性将瞬间崩塌。需要警惕的是，GCC 与 Clang 的内建指令 __builtin_clz(0) 在硬件层面直接构成未定义行为，我们在 21.6 节调用它之前必须在此处的外围包装中严密拦截零输入。

头文件里的声明：

c
/* 前导零、尾随零的个数；输入为 0 时返回位宽（32 或 64），与 C23 <stdbit.h> 一致。 */
unsigned mdr_clz_u32(uint32_t x);
unsigned mdr_clz_u64(uint64_t x);
unsigned mdr_ctz_u32(uint32_t x);
unsigned mdr_ctz_u64(uint64_t x);

最直观的实现是从最高位往下数，用左移把每一位送到最高位检查：

c
unsigned mdr_clz_u32(uint32_t x) {
    unsigned n = 0;

    if (x == 0) {
        return 32;
    }
    while ((x & 0x80000000u) == 0) {
        x <<= 1;
        n++;
    }
    return n;
}

在上述朴素逐位扫描实现中，当输入仅有最低位为 1 时，代码最坏需要循环迭代 31 次。而在工业级位运算中，通常采用类似二分查找的分治策略：每次利用位掩码探测当前高半部分是否全为 0，若是则将计数器累加对应权重并将低半部分左移上来，从而在固定的 5 次二分判断内彻底完成 32 位整数的扫描：

c
unsigned mdr_clz_u32(uint32_t x) {
    unsigned n = 0;

    if (x == 0) {
        return 32;
    }
    if ((x & 0xFFFF0000u) == 0) {
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000u) == 0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000u) == 0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000u) == 0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000u) == 0) {
        n += 1;
    }
    return n;
}

两版的对照输出：

zsh - clz_demo
text
$ gcc -std=c17 -Wall -Wextra -O2 clz_demo.c -o clz_demo
$ ./clz_demo
00000000  loop 32  binary 32
00000001  loop 31  binary 31
00000002  loop 30  binary 30
0000FFFF  loop 16  binary 16
00010000  loop 15  binary 15
80000000  loop  0  binary  0
FFFFFFFF  loop  0  binary  0

对于统计末尾连续零个数的 mdr_ctz_u32，我们甚至无需重复编写一套对称的分治循环，而是可以巧妙借用前导零的结果。在计算机位运算代数中，表达式 x & (0u - x)（即保留最低有效位的经典技巧）能够精准剥离并保留 x 中最低位的那颗孤立的 1，其余所有位全部归零。通过前导零函数计算出该孤立 1 在 32 位空间中的高位偏移后，用 31 减去该值即可精确换算出其低位尾随零的个数：31 - mdr_clz_u32(x & (0u - x))。其中 0u - x 是纯粹良定义的无符号补码取负，在模 2^32 下严格成立：

c
unsigned mdr_ctz_u32(uint32_t x) {
    if (x == 0) {
        return 32;
    }
    return 31 - mdr_clz_u32(x & (0u - x));
}

把 x & (0u - x) 单独打印出来，能看清它取到的是哪一位：

zsh - tz_demo
text
$ gcc -std=c17 -Wall -Wextra -O2 tz_demo.c -o tz_demo
$ ./tz_demo
00000000  ctz 32  lowest bit 00000000
00000001  ctz  0  lowest bit 00000001
00000002  ctz  1  lowest bit 00000002
00010000  ctz 16  lowest bit 00010000
80000000  ctz 31  lowest bit 80000000
60000000  ctz 29  lowest bit 20000000

最后一行值得停一下：0x60000000 的第 29 位是第一个 1，x & (0u - x) 得到 0x20000000，恰好是 2^29。

在编写 64 位版本时，只需将最高位掩码替换为对应的 64 位无符号字面量宏 UINT64_C(0x8000000000000000)，逻辑结构完全一致。使用标准宏 UINT64_C 的关键在于确保常量具备与 uint64_t 完全一致的真实底层类型：在 64 位 Linux（LP64 数据模型）中该类型通常为 unsigned long，而在 64 位 Windows（LLP64 数据模型）中则被定义为 unsigned long long。如果随意在代码中硬编码原始字面量，其推导类型极易在不同操作系统间发生偏移，进而在配合 %llu 打印或参与泛型宏计算时引发级联编译告警。

对于统计算法，mdr_popcount_u64 继续延续我们在第一部分建立的经典 Brian Kernighan 算法，利用 x &= x - 1 每次从低向高精准剥离一个 1，循环次数严格等于输入中 1 的真实总数。而对于校验奇偶性（Parity）的接口，其核心目标是获取 1 的总数的最低有效位（即奇偶性），此时甚至无需完整数出数量，通过折半异或（Fold XOR）树状结构将高半部分比特逐级压缩折叠到低半部分，最终提取最低位即可：

c
unsigned mdr_parity_u32(uint32_t x) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1u;
}

3. 2 的幂 ​

在内存池管理与数据对齐中，针对 2 的整数次幂的判定与规整是出镜率极高的基础操作。上述四个核心接口全部优雅地建立在 mdr_clz_u32 这一基础设施之上。

首先，判定一个数是否恰好是 2 的整数次幂，可以通过位代数短语 x != 0 && (x & (x - 1)) == 0 在常数时间内裁定：因为 2 的幂在二进制表示中有且仅有一位是 1，对其减 1 之后，该位变为 0 且其下方所有低位全部翻转为 1，两者按位与的结果必然严格为 0。

接口原型声明如下：

c
bool mdr_has_single_bit_u32(uint32_t x);

unsigned mdr_bit_width_u32(uint32_t x);   /* 表示 x 需要的最少位数，0 返回 0 */

uint32_t mdr_bit_floor_u32(uint32_t x);   /* 不超过 x 的最大 2 的幂，0 返回 0 */

uint32_t mdr_bit_ceil_u32(uint32_t x);    /* 不小于 x 的最小 2 的幂，放不下返回 0 */

在语义设计上：

  • mdr_bit_width_u32(x) 计算表示数值 x 所必须的最少有效二进制位数，其值等价于 32 - mdr_clz_u32(x)；当输入为 0 时，自然得到 0。
  • mdr_bit_floor_u32(x) 用于求出小于等于 x 的最大 2 的整数次幂，只需将最高位的那个 1 保留，其余低位全部抹零，即 1u << (31 - mdr_clz_u32(x))。
  • mdr_bit_ceil_u32(x) 则用于向上寻找大于等于 x 的最小 2 的整数次幂。此处的实现边界最为微妙：为了防止当输入本身已经是 2 的整数次幂时错误地多算了一倍，最干净的做法是在进入计算前先执行减 1 预处理：
c
uint32_t mdr_bit_ceil_u32(uint32_t x) {
    if (x <= 1) {
        return 1;
    }
    if (x > 0x80000000u) {
        return 0;
    }
    return 1u << (32 - mdr_clz_u32(x - 1));
}

在 mdr_bit_ceil_u32 中，x > 0x80000000u 这一显式分支至关重要：由于 32 位无符号整型能够表示的最大 2 的幂就是 2^31（即 0x80000000），一旦输入大于该极值，其数学上的最小 2 的幂上限为 2^32，已经彻底超出了 uint32_t 的物理表达上限。按照 C23 标准 <stdbit.h> 的规定，此时函数必须确定地返回 0。Linux glibc 2.41 提供的 stdc_bit_ceil_ui(0x80000001u) 同样严格返回 0。这种以 0 作为溢出哨兵的设计极其干净利落，因为 0 绝不可能是任何正整数向上取整后的有效 2 的幂，调用方仅凭单次非零判断即可立即洞察容量溢出。

在支持 C23 的 Linux 机器上，把四个函数与 <stdbit.h> 逐个对照：

c
for (uint32_t x = 0; x <= 0xFFFFu; x++) {
    bad += mdr_has_single_bit_u32(x) != stdc_has_single_bit_ui(x);
    bad += mdr_bit_width_u32(x) != stdc_bit_width_ui(x);
    bad += mdr_bit_floor_u32(x) != stdc_bit_floor_ui(x);
    bad += mdr_bit_ceil_u32(x) != stdc_bit_ceil_ui(x);
}
zsh - bit_table
text
$ gcc -std=c23 -Wall -Wextra -Iinclude bit_table.c src/mdr_bits.c -o bit_table
$ ./bit_table
         x width  bit_floor   bit_ceil  stdc_ceil
         0     0          0          1          1
         1     1          1          1          1
         2     2          2          2          2
         3     2          2          4          4
        FF     8         80        100        100
       100     9        100        100        100
  80000000    32   80000000   80000000   80000000
  80000001    32   80000000          0          0
16-bit check against <stdbit.h>: 0 mismatches

本机 MinGW-w64 GCC 13.2 没有 <stdbit.h>，这几个函数只能用第 7 节的慢速参照实现来测；__has_include(<stdbit.h>) 在本机为假，Linux 上 GCC 14.2 为真，21.6 用这个宏决定走哪条路。

单选

按本节的规格，mdr_bit_ceil_u32(0) 返回什么？

0
1
0x80000000
未定义，取决于编译器

4. 循环移位与字节序 ​

在实现循环移位（Rotate Left / Rotate Right）时，最为棘手的边界恰恰发生在移位量为 0 的极端情形。如果按照直觉直接写出 (x << k) | (x >> (32 - k))，当传入的 k 为 0 时，表达式右半部分会演变为 x >> 32，这瞬间触发了我们在前文强调过的未定义行为法则——移位位数等于类型宽度。

为了彻底抹平这一未定义风险，稳健的做法分为两步：首先将外部传入的移位参数 k 通过 k &= 31 模归一化到 0 到 31 的有效位移区间内；其次，对反向移位的偏移量同样追加一次 & 31 掩码截断：

c
uint32_t mdr_rotl_u32(uint32_t x, unsigned k) {
    k &= 31;
    return (x << k) | (x >> ((32 - k) & 31));
}

uint32_t mdr_rotr_u32(uint32_t x, unsigned k) {
    k &= 31;
    return (x >> k) | (x << ((32 - k) & 31));
}

在上述修正实现中，当 k 为 0 时，左半部分为 x << 0 保持原值，右半部分计算 (32 - 0) & 31 同样精确收敛为 0，从而安全求得 x >> 0，最终结果保持原值无损；当外部传入 32 时，第一行 k &= 31 同样将其规整为 0。在规格中，我们明确声明「移位量统一按 k % 32 映射」，因此调用方即便传入 32、33 甚至更大的正整数，函数也能平稳交出合规的循环移位值。

❌ 移位量为 0 时越界
c
uint32_t mdr_rotl_u32(uint32_t x, unsigned k) {
    return (x << k) | (x >> (32 - k));
}
✅ 先掩码再移位
c
uint32_t mdr_rotl_u32(uint32_t x, unsigned k) {
    k &= 31;
    return (x << k) | (x >> ((32 - k) & 31));
}

左栏在 k 等于 0 时右移 32 位，在 k 大于等于 32 时两个移位都越界。UBSan 构建下调用 rotl_naive(x, 0)：

zsh - shift_naive
text
$ gcc -std=c17 -Wall -Wextra -g -fsanitize=undefined -fno-sanitize-recover=all shift_naive.c -o shift_naive
$ ./shift_naive
shift_naive.c:5:26: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
$ echo $?
1

右栏的版本在同样的构建里跑 k = 0..63：

zsh - shift_ub
text
$ gcc -std=c17 -Wall -Wextra -g -fsanitize=undefined -fno-sanitize-recover=all shift_ub.c -o shift_ub
$ ./shift_ub
k = 0..63 done
$ echo $?
0

同一个程序在 -O2 下还能被编译器精准识别。把移位量固定成 7 时，生成的目标代码直接被合成为一条硬件循环移位指令 roll：

asm
mdr_rotl_u32:
	movl	%ecx, %eax
	movl	%edx, %ecx
	roll	%cl, %eax
	ret

这是 MinGW-w64 GCC 13.2、-O2 -S 的输出；Linux 上 GCC 14.2 生成同样的 roll %cl, %eax，只是参数寄存器换成 %edi、%esi。循环移位写成移位加或之后，编译器能够自动将其重写为最简硬件指令，完全不需要为它单独编写晦涩的内联汇编。

字节交换的 64 位版本由第一部分的 mdr_bswap32 拼出来，高低两半各换一次，再交换位置：

c
uint64_t mdr_bswap64(uint64_t x) {
    return ((uint64_t)mdr_bswap32((uint32_t)x) << 32) |
           mdr_bswap32((uint32_t)(x >> 32));
}

读写文件格式用的四个函数与主机字节序无关：它们按字节下标组装或拆解，不经过 uint32_t 在内存里的布局。小端是先低字节后高字节，大端反过来：

c
uint32_t mdr_load_le32(const void *src) {
    const unsigned char *p = (const unsigned char *)src;

    return (uint32_t)p[0] | ((uint32_t)p[1] << 8) | ((uint32_t)p[2] << 16) |
           ((uint32_t)p[3] << 24);
}

uint32_t mdr_load_be32(const void *src) {
    const unsigned char *p = (const unsigned char *)src;

    return ((uint32_t)p[0] << 24) | ((uint32_t)p[1] << 16) |
           ((uint32_t)p[2] << 8) | (uint32_t)p[3];
}

mdr_store_le32 与 mdr_store_be32 逻辑相反，先逐级右移再用 0xFF 掩码，逐个写入字节缓冲区。参数写成 const void * 是为了能从任意物理缓冲区读取，函数内部必须转换成 unsigned char *，否则在 char 为有符号的平台上，0x80 以上的字节会先补符号位再移位。

写一串字节再读回来，两边机器给出同一个值：

zsh - roundtrip
text
$ gcc -std=c17 -Wall -Wextra roundtrip.c -o roundtrip
$ ./roundtrip
host layout of value: 78 56 34 12
load_le32 -> 12345678

第一行是 0x12345678 这个对象在本机内存里的字节顺序，x86-64 属于小端架构，所以最低字节 0x78 排在最前。第二行则是基于小端规则解析出的逻辑数值。在 Linux 环境下运行同一份程序，两行输出逐字相同；若将程序迁移到纯大端架构上执行，第一行会自动变为 12 34 56 78，而第二行依据小端规则还原的值依然稳定为 12345678。在处理磁盘持久化文件或跨主机网络协议中的整数时，必须使用这组函数，切忌直接使用 memcpy 把裸内存强行复制到整型对象中并寄希望于两端架构碰巧兼容。

多选

关于本节这几个函数，下列说法正确的是哪些？

mdr_rotl_u32(x, 32) 与 mdr_rotl_u32(x, 0) 结果相同
mdr_rotl_u32 的返回值恒等于 x
mdr_load_le32 的返回值取决于主机的字节序
mdr_bswap64(mdr_bswap64(x)) 等于 x

5. 带检查的算术 ​

在涉及堆内存分配的代码中，最为凶险的潜在漏洞往往潜伏在 malloc(n * size) 这一看似无害的乘法计算中。如果操作数 n 与单个结构体大小 size 均为 size_t，当两者乘积超出 2^64 时，算术运算会无声无息地回绕为一个极其微小的正整数。此时 malloc 会按照这个截断后的小尺寸成功分配缓冲区，而后续的循环却依然固执地按 n 次迭代向堆内存大肆写入，瞬间酿成致命的堆越界写破坏。

要在标准 C 中安全判定乘法溢出，必须逆向借助除法进行边界预判：只要乘数 b != 0，若有 a > SIZE_MAX / b 成立，则两者的乘积必然超出 size_t 的物理表达界限。由于除法计算绝不会引发溢出，这一预判逻辑在代数上具备坚固的安全性：

c
bool mdr_ckd_mul_size(size_t a, size_t b, size_t *res) {
    if (b != 0 && a > SIZE_MAX / b) {
        return true;
    }
    *res = a * b;
    return false;
}

同理，无符号加法的溢出检测应当逆向借助减法来实现：若有 a > SIZE_MAX - b，则说明两者相加必然发生模进位溢出。由于此时必有 b <= SIZE_MAX，减法表达式 SIZE_MAX - b 绝不会发生下溢回绕，因而判断过程完全安全自洽：

c
bool mdr_ckd_add_size(size_t a, size_t b, size_t *res) {
    if (a > SIZE_MAX - b) {
        return true;
    }
    *res = a + b;
    return false;
}

在接口返回值契约上，我们明确约定「发生溢出时返回 true，未发生溢出时返回 false」，这与 C23 标准正式引入的 <stdckdint.h> 头文件中的 ckd_add 族宏规范保持了高度同步。通过布尔值明确指示溢出状态、将计算结果通过指针参数安全传出的设计，能够有效避免旧式 C 库中混用 0 与 -1 充当状态标志所带来的可读性困扰。

用它检查几个分配大小：

zsh - ckd_demo
text
$ gcc -std=c17 -Wall -Wextra -Iinclude ckd_demo.c src/mdr_bits.c -o ckd_demo
$ ./ckd_demo
small            n=40 size=16 -> 640 bytes
large            n=1099511627776 size=16 -> 17592186044416 bytes
exact-max        n=9223372036854775807 size=2 -> 18446744073709551614 bytes
just-over        n=9223372036854775808 size=2 -> overflow

exact-max 一行的乘积是 2^64 - 2，离上限只差 1，没有溢出；元素数再多一个就报溢出了。large 一行是 16 TiB，照样算得出来——这个函数检查的只是乘积能不能用 size_t 表示，不是内存够不够。这两件事要分开：求出来的大小能不能分配由 malloc 回答，参数相乘会不会溢出由这个函数回答。

有符号加法的检查不能照搬上面的减法，因为 SIZE_MAX - b 那一步在有符号类型里可能已经越界。先拿 INT_MAX - b 比，比完再相加：

c
#include <limits.h>

bool ckd_add_int(int a, int b, int *res) {
    if (b > 0 ? a > INT_MAX - b : a < INT_MIN - b) {
        return true;
    }
    *res = a + b;
    return false;
}

饱和加法是另一类需求：图形和音频里希望结果停在最大值，而不是回绕。先用 uint64_t 把和算出来，再与 UINT32_MAX 比：

c
uint32_t mdr_sat_add_u32(uint32_t a, uint32_t b) {
    uint64_t sum = (uint64_t)a + b;

    return sum > UINT32_MAX ? UINT32_MAX : (uint32_t)sum;
}

(uint64_t)a 这个转换不能省：两个 uint32_t 直接相加会在 32 位里回绕。

6. 对齐与取整 ​

在底层内存管理、页表映射与缓存行对齐的计算中，将一个数值向上规整到 2 的整数次幂的倍数是标准的惯用语法：先加上 align - 1，随后利用位与运算抹掉全部低位比特：

c
size_t mdr_align_up_size(size_t x, size_t align) {
    return (x + align - 1) & ~(align - 1);
}

表达式 ~(align - 1) 能够精准生成低位全为 0、高位全为 1 的位掩码，通过按位与运算便能只保留属于 align 整数倍的高阶成分。需要强调的是，这一位运算技巧严格要求基准对齐量 align 必须是 2 的整数次幂；若调用方传入任意奇数或其他非 2 的幂数值，掩码将彻底失效。我们在接口头文件的前置条件中明确写明了这一契约约束。

跑一组值：

zsh - align_demo
text
$ gcc -std=c17 -Wall -Wextra -Iinclude align_demo.c src/mdr_bits.c -o align_demo
$ ./align_demo
align_up( 0, 8) =  0
align_up( 1, 8) =  8
align_up( 8, 8) =  8
align_up( 9, 8) = 16
align_up(13, 8) = 16
align_up(16, 8) = 16
align_up(17, 8) = 24
div_ceil(0, 4) = 0
div_ceil(5, 4) = 2
div_ceil(SIZE_MAX, 2) = 9223372036854775808

已经对齐的值原样返回，多出一点就跳到下一个倍数。最后一行是向上取整除法不溢出的证据：SIZE_MAX 除以 2 得 2^63 - 1，余 1，于是结果加一，得到 2^63。用 (a + b - 1) / b 算，a + b - 1 在这一步回绕，结果完全不同。

而在计算离散资源分配时，向上取整除法（Ceil Division）同样极易滋生溢出缺陷。初学者极其习惯于写出经典的 (a + b - 1) / b 宏，然而该公式潜藏着严重的安全死角：当被除数 a 本身已经极其接近 SIZE_MAX 时，括号内的 a + b - 1 会在进入除法之前率先发生模进位回绕，导致计算出的商沦为一个荒谬的微小数值。

为了杜绝此类隐患，应当改为在代数上完全杜绝加法溢出的「先整除后补余」策略：

c
size_t mdr_div_ceil_size(size_t a, size_t b) {
    return a / b + (a % b != 0);
}
❌ 先加后除，可能溢出
c
size_t div_ceil(size_t a, size_t b) {
    return (a + b - 1) / b;
}
✅ 先除后补，不溢出
c
size_t mdr_div_ceil_size(size_t a, size_t b) {
    return a / b + (a % b != 0);
}

对比左右两栏的逻辑可知：左栏的写法将溢出风险完全暴露在事前加法中；而右栏的重构版本每一步都在安全范围内展开——整除 a / b 的结果必然不大于 a，取模余数 a % b 严格小于除数 b，末尾的三元增量最多使商增加 1。在计算分页系统中「容纳指定字节流需要多少物理页」时，必须坚决采用右栏这一不会引发溢出的稳妥算法。

二分查找中计算中点坐标的经典演进也是同一个原理的生动写照：写法 (lo + hi) / 2 在两个下标均处于大数值区间时极易遭遇加法溢出，而将其重写为 lo + (hi - lo) / 2 后，由于差值 hi - lo 严格局限在区间长度内，再加上基准 lo 也绝不会突破 hi，从而在根本上保障了算术的自洽与安全。

c
size_t mid = lo + (hi - lo) / 2;

这三处（对齐、取整、中点）的共同点是先把运算压到安全范围里，再组合。写这类辅助函数时，值得在规格注释里把「调用方保证什么」写清楚，例如 mdr_align_up_size 的「align 是 2 的幂」，别的读者才不会传 24 进来。

7. 测试位操作函数 ​

位操作函数具备一项独特的测试优势：对于 16 位及以下的输入空间，我们完全有能力进行全量穷举验证。编写一个逻辑极其直白、逐位展开处理的基准参考实现，虽然运算效率不高，但其正确性一目了然，非常适合拿来与高度优化的位运算函数逐一核对。

c
/* 逐位循环的参照实现：慢，但一眼能看出对错 */
static unsigned ref_clz_u32(uint32_t x) {
    unsigned n = 0;

    for (int bit = 31; bit >= 0; bit--) {
        if (((x >> (unsigned)bit) & 1u) != 0) {
            break;
        }
        n++;
    }
    return n;
}

这种测试思路的核心在于“参照实现保真、目标实现求快”。全量遍历 16 位无符号整数全部 65536 种状态，现代处理器往往只需几毫秒即可验证完毕：

zsh - exhaustive
text
$ gcc -std=c17 -Wall -Wextra -O2 exhaustive.c -o exhaustive
$ ./exhaustive
16-bit values: 65536, mismatches: 0
32-bit boundary values: 14, mismatches: 0
rotate properties: ok

对于 32 位甚至 64 位无符号整数，遍历全部状态空间在时间上并不现实。此时测试策略主要转向两个方向：一是精心构造边界值集合，二是基于代数性质进行一致性校验。

边界集合通常选取 0、1、2、3、各类形如 2k 与 2k±1 的数值，以及全 1 掩码（如 0xFFFFFFFF），这类数值能够精准覆盖条件分支与进位边界。而性质检查（Property-based testing）则不依赖逐项对照的参考实现，转而验证数学上恒成立的自洽关系：

  • mdr_rotl_u32(mdr_rotr_u32(x, k), k) == x：左右旋转操作互为逆运算。
  • mdr_bswap64(mdr_bswap64(x)) == x：连续进行两次字节序反转应当还原数值。
  • mdr_popcount_u64(x) + mdr_popcount_u64(~x) == 64：任意数值与其按位取反值的置 1 位数之和恒等于总位宽。

在测试逻辑中用循环对海量数值验证上述代数恒等式，比起硬编码少量静态输入与期望输出，对边缘逻辑漏洞的捕捉能力要严密得多。

在工程实践中，测试源文件 tests/test_bits.c 沿用轻量断言宏 check.h，将这些特异值与性质验证组织成标准测试集：

c
static void test_power_of_two(void) {
    CHECK(!mdr_has_single_bit_u32(0u));
    CHECK(mdr_has_single_bit_u32(1u));
    CHECK(mdr_has_single_bit_u32(0x80000000u));
    CHECK(!mdr_has_single_bit_u32(0x80000001u));

    CHECK(mdr_bit_ceil_u32(0u) == 1u);
    CHECK(mdr_bit_ceil_u32(0x80000000u) == 0x80000000u);
    CHECK(mdr_bit_ceil_u32(0x80000001u) == 0u);
}

执行完整的测试套件：

zsh - ctest
text
$ cmake -S . -B build
$ cmake --build build -j2
$ ctest --test-dir build --output-on-failure
Test project /home/minsecrus/tutorial/work/p067/build
    Start 1: test_bits
1/3 Test #1: test_bits ........................   Passed    0.00 sec
    Start 2: test_memory
2/3 Test #2: test_memory ......................   Passed    0.00 sec
    Start 3: test_string
3/3 Test #3: test_string ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 3

Total Test time (real) =   0.01 sec
$ ./build/test_bits
test_bits: 99 checks, 0 failed

此时 test_bits 的断言数量已扩充到 99 项，与前文实现的内存、字符串测试一同构成了扎实的阶段回归基线。后续章节还将引入强制纯 C 回退的对照库与自动化差分测试，在不同编译目标与运行路径下反复交叉印证。在 Windows 环境下配合 Ninja 构建运行，测试用例同样全部通过。

除了常规的功能断言，借助未定义行为检查器（UBSan, UndefinedBehaviorSanitizer）也能帮我们发现潜在的位移越界。例如让循环移位的步长遍历一个完整的周期乃至超长范围，观测是否存在未受掩码保护的非法移位操作：

c
/* tests/test_bits.c 里没有的临时检查：绕一圈移位 */
for (unsigned k = 0; k < 64; k++) {
    bad += mdr_rotr_u32(mdr_rotl_u32(x, k), k % 32u) != x;
    bad += mdr_rotl_u32(mdr_rotr_u32(x, k), k % 32u) != x;
}
zsh - UBSan
text
$ gcc -std=c17 -Wall -Wextra -g -fsanitize=undefined -fno-sanitize-recover=all \
    -Iinclude ub_rot.c src/mdr_bits.c -o ub_rot
$ ./ub_rot
k = 0..63 done, round-trip failures: 0
$ echo $?
0

添加编译选项 -fno-sanitize-recover=all 可以确保只要触发任何一处未定义行为，程序就会立刻中断退出，而不是打印警告后带着被污染的状态继续运行。在持续集成中，若缺少此项配置，UBSan 默认的宽松策略很可能让包含违规移位的测试在表面上依然返回 0 并误判为「通过」。

MinGW 上的 Sanitizer

某些 MinGW-w64 GCC 发行版本可能未随附 UBSan 运行时库，在链接时会提示 cannot find -lubsan。此时可在 Linux 环境或 WSL 中执行 Sanitizer 构建；在 Windows 原生开发时，也可使用 MSVC 或其配套的 Clang 工具链开启 ASan 与 UBSan 支持。若本地环境暂不支持运行时插桩，在代码审查阶段严格推导移位掩码与边界条件同样必不可少。

8. 习题 ​

8.1 巩固 ​

#22141
⚡2⏳2

这段程序和正文的整数提升例子只差几个常量：

c
#include <stdint.h>
#include <stdio.h>

int main(void) {
    uint8_t byte = 0x0F;
    uint16_t word = 0xFFFF;

    printf("~byte       = %08X\n", (unsigned)~byte);
    printf("byte << 4   = %08X\n", (unsigned)(byte << 4));
    printf("word * word = %08X\n", (unsigned)(word * word));
    printf("(uint16_t)word * word = %04X\n", (unsigned)(uint16_t)(word * word));
    printf("sizeof(byte + byte) = %lu\n", (unsigned long)sizeof(byte + byte));
    return 0;
}

(1) 写出五行输出。

(2) 解释第四行与第三行差在哪里：乘法本身在什么类型里完成，截断发生在哪一步。

(3) 有一个函数要清掉 uint8_t 值的第 4 位，写成 x &= ~(1u << 4);，x 声明为 uint8_t。这一行在 -Wall -Wextra 下没有任何警告，加上 -Wconversion 才会报 conversion from 'unsigned int' to 'uint8_t' changes the value。解释这个警告的来历（~ 的结果是 32 位、复合赋值要把它转回 8 位），再写出两种加不加 -Wconversion 都干净的写法。

#22142
⚡2⏳2

按本节的规格手算下面这张表，不运行程序：

xmdr_clz_u32(x)mdr_ctz_u32(x)mdr_bit_width_u32(x)x & (0u - x)
0x00000000
0x00000001
0x0000000F
0x00100000
0x80000000
0xF0000000

(1) 填完表格，并写出每一行的 mdr_ctz_u32 至少一种算法（31 - clz(x & -x) 或逐位右移）算出的中间值。

(2) mdr_bit_width_u32(0) 等于 0，mdr_clz_u32(0) 等于 32。如果实现把 bit_width 写成 31 - clz(x)，这两行的结果分别变成多少？说明为什么规格里「输入为 0 时返回位宽」这一条不能省。

(3) 下面这个 mdr_popcount_u32 变体把 x &= x - 1 换成了 x >>= 1，指出它实际数的是什么，并给出两个结果不同的具体输入：

c
unsigned popcount_bug(uint32_t x) {
    unsigned count = 0;

    while (x != 0) {
        x >>= 1;
        count++;
    }
    return count;
}

x 为 0xFF 时两个版本碰巧都给 8，说明为什么这一组不能用来证明变体正确。再写出一个输入，使两个结果相差最大。

#22143
⚡3⏳3

下面四个函数都按「先想清楚规格、再写代码」的方式检查：

c
uint32_t mdr_rotl_u32(uint32_t x, unsigned k);
uint32_t mdr_rotr_u32(uint32_t x, unsigned k);
uint64_t mdr_bswap64(uint64_t x);
uint32_t mdr_bit_ceil_u32(uint32_t x);

(1) 写出 mdr_rotl_u32(0x12345678u, k) 在 k 为 0、1、4、31、32、33、63 时的值。

(2) mdr_rotl_u32 的实现是 k &= 31; return (x << k) | (x >> ((32 - k) & 31));。把 k 的类型从 unsigned 改成 int 后传 -1，函数还能给出规格要求的结果吗？说明 k &= 31 在这一步做了什么。

(3) 64 位循环移位需要 k % 64。写 mdr_rotl_u64(0x0123456789ABCDEFull, k) 与 mdr_rotr_u64，说明 (64 - k) & 63 里的 & 63 为什么不能省。要求对 k 为 0、1、32、64、65 各给出结果。

(4) mdr_bswap64(0x0102030405060708ull) 等于多少？用两个 mdr_bswap32 拼出来的实现里，高 32 位与低 32 位各自先换还是后换，会不会影响结果？

8.2 编程 ​

#22144
⚡3⏳3

按本节的方法给旋转函数做性质测试，不依赖期望值表：

c
/* 对给定的一组 x，检查
 *   mdr_rotl_u32(mdr_rotr_u32(x, k), k) == x
 *   mdr_rotr_u32(mdr_rotl_u32(x, k), k) == x
 *   mdr_rotl_u32(x, k + 32) == mdr_rotl_u32(x, k)
 * 三个性质对 k = 0..127 全部成立 */
static unsigned check_rotate(uint32_t x, unsigned *first_bad_k);

要求：

  1. 在 {0, 1, 0x80000000u, 0xFFFFFFFFu, 0x12345678u, 0xAAAAAAAAu} 上跑，全部通过，打印每个 x 的检查次数。
  2. 故意把 mdr_rotl_u32 的移位量掩码去掉（写成 return (x << k) | (x >> (32 - k));），用 -fsanitize=undefined -fno-sanitize-recover=all 构建，报告程序在第几个 x、哪个 k 上被终止，并贴出 UBSan 的错误行。MinGW 上没有 UBSan 运行库时，改为在 Linux 上做，或说明跳过原因。
  3. 把被测函数换成你写的 64 位版本，用 k = 0..127 再跑一遍。指出 k 恰好等于 64 的倍数时，两个方向各移动多少位。

验收：修好的版本在普通构建与 UBSan 构建下都以状态 0 退出，性质检查全部通过；错误版本在 UBSan 下以非零状态退出并指出越界移位。

#22145
⚡3⏳3

读写文件格式时，整数按固定字节序存储。实现下面四个函数，并在同一份程序里完成两组验收：

c
uint32_t mdr_load_le32(const void *src);
void mdr_store_le32(void *dst, uint32_t x);
uint64_t mdr_load_le64(const void *src);
void mdr_store_le64(void *dst, uint64_t x);

(1) 字节序往返。对 0x12345678u 与 0x0123456789ABCDEFull，先 store_le 再逐字节打印，再 load_le 读回，要求打印的值与写入相同。字节序列分别是 78 56 34 12 与 EF CD AB 89 67 45 23 01。把同一份程序在一台大端机器上跑（没有时说明输出哪一行会变、哪一行不变），确认读回的值不变。

(2) 变长整数（LEB128）。一个无符号整数从低位起每 7 位一组，除最后一组外每组最高位置 1，最后一组最高位为 0：

text
0          -> 00
1          -> 01
127        -> 7F
128        -> 80 01
300        -> AC 02
624485     -> E5 8E 26
4294967295 -> FF FF FF FF 0F

写 size_t mdr_varint_encode(uint64_t v, unsigned char *out) 与 int mdr_varint_decode(const unsigned char *in, size_t n, uint64_t *out, size_t *used)。解码时遇到 n 个字节还没见到最高位为 0 的组，返回 -1；out 与 used 在成功时写入结果与消耗的字节数。

验收：编码上表七个值，结果逐个对照；再用解码器读回，值与消耗字节数都对。另外构造只含 80（缺后续组）和 80 80 80 80 80 80 80 80 80 02（十个字节，最后一组的值要放在第 63 位，超出 uint64_t）两种输入，说明解码器各自返回什么，为什么。FF FF FF FF FF FF FF FF FF 01 是合法的最大值，解码结果是 UINT64_MAX，把它一并作为对照。

#22146
⚡4⏳3

带检查的算术要覆盖减法与有符号数。实现：

c
bool mdr_ckd_sub_size(size_t a, size_t b, size_t *res);   /* a - b 下溢返回 true */
bool mdr_ckd_mul_size(size_t a, size_t b, size_t *res);   /* 已实现，复用 */
uint32_t mdr_sat_add_u32(uint32_t a, uint32_t b);          /* 已实现，复用 */
uint32_t mdr_sat_sub_u32(uint32_t a, uint32_t b);          /* 新实现 */

(1) 写 mdr_ckd_sub_size，只用比较，不依赖结果是否变大。写出规格：下溢的判断条件、res 在返回 true 时是否被写入（你的选择要写进注释，并说明理由）。

(2) 用正文的检查思路实现 mdr_sat_sub_u32：a < b 时返回 0，否则返回 a - b。给出 (0, 0)、(5, 3)、(3, 5)、(UINT32_MAX, UINT32_MAX) 四组结果。

(3) 写一个测试程序，对 mdr_ckd_mul_size 跑这些组合：(0, SIZE_MAX)、(1, SIZE_MAX)、(SIZE_MAX, 1)、(SIZE_MAX, 2)、(SIZE_MAX / 2, 2)、(SIZE_MAX / 2 + 1, 2)。每一组写出期望的返回值与（未溢出时）乘积，实际运行后对照。

(4) 在支持 C23 的环境里，把 (3) 的结果与 <stdckdint.h> 的 ckd_mul 对照。两者返回值的含义是否一致？如果不一致，写一个适配层把其中一方翻过来。

#22147
⚡4⏳4

对齐与取整的三个函数都只对 2 的幂成立，调用方一旦传了别的值就静默出错。补一个通用版本并做对照：

c
/* 把 x 向上对齐到 align 的倍数，align 为任意正整数。 */
size_t mdr_align_up_any(size_t x, size_t align);

/* 把 x 向下对齐到 align 的倍数。 */
size_t mdr_align_down_size(size_t x, size_t align);

/* 覆盖 [0, bytes) 需要多少个大小为 page 的页，page 不为 0。 */
size_t mdr_pages_needed(size_t bytes, size_t page);

(1) 实现三个函数，要求每一步都不溢出：不能写 (x + align - 1) / align * align 这类先加后除的式子，也要说明 x + (align - x % align) % align 为什么在 x 接近 SIZE_MAX 时会回绕，改成什么写法才安全。

(2) 对 align 为 6（不是 2 的幂）跑 x = 0, 7, 10, 13，把 mdr_align_up_size 与 mdr_align_up_any 的结果并排列出，指出前者在哪几个值上错、错成什么。

(3) mdr_div_ceil_size 与 mdr_pages_needed 有什么关系？给出 bytes 为 0、1、page、page + 1、SIZE_MAX、page 为 1 时的结果，并说明 SIZE_MAX 一组为什么不会溢出。

(4) 二分查找的中点 lo + (hi - lo) / 2 在 lo = SIZE_MAX - 2、hi = SIZE_MAX 时等于多少？写成 (lo + hi) / 2 又得到多少？把这两个数写成十六进制。

8.3 综合与挑战 ​

#22148
⚡5⏳4

下面的 bit_ceil 用位宽代替「先减一」，看起来更直白：

c
uint32_t bit_ceil_bug(uint32_t x) {
    if (x == 0) {
        return 1;
    }
    if (x > 0x80000000u) {
        return 0;
    }
    return (uint32_t)(1ull << mdr_bit_width_u32(x));
}

用 1ull 而不是 1u，是为了让 x 为 0x80000000 时移位 32 位仍有定义（结果再截断到 32 位）。

(1) 对 x = 0, 1, 2, 3, 4, 5, 0x80000000 列出 bit_ceil_bug 与正确值的对照表，指出哪一类输入必然错。

(2) 在 0..0xFFFF 上穷举，统计与正确实现不一致的输入个数，并列出这些值。个数是 16；x 为 0 时两个实现都返回 1，所以 0 不在其中。解释为什么不一致的集合正好是「不大于 0x8000 的 2 的幂」。

(3) 用正文第 7 节的做法写一个完整的测试程序 test_bit_ceil：包含 16 位穷举、32 位边界值（0、1、2、3、2^k、2^k ± 1、0xFFFFFFFF）和性质检查 mdr_bit_ceil_u32(x) >= x、mdr_has_single_bit_u32(mdr_bit_ceil_u32(x))（返回值非 0 时）。要求错误版本至少被一组检查抓住，修好的版本全部通过。

(4) 把 0xFFFFFFFF 一组单独拿出来：正确版本返回 0，bit_ceil_bug 也返回 0。为什么这一组不能作为「实现正确」的证据？指出它掩盖了哪个分支的缺陷。

#22149
⚡6⏳5

把本节的函数组合成一个分配大小计算工具，这是它们在工程里的典型用法。接口：

c
/* 计算 n 个元素、每个 size 字节的分配请求。
 * 结果写入 *bytes（对齐后的字节数）与 *pages（页数）。
 * 乘法溢出、对齐加法溢出、页数溢出都返回 false，且不写入输出参数。 */
bool mdr_alloc_plan(size_t n, size_t size, size_t align, size_t page,
                    size_t *bytes, size_t *pages);

/* 把请求的字节数上调到不小于它的 2 的幂，已是对齐粒度的倍数；
 * 结果放不下时返回 0。 */
size_t mdr_alloc_round(size_t bytes);

要求：

  1. 用 mdr_ckd_mul_size、mdr_align_up_size、mdr_div_ceil_size、mdr_bit_ceil_u32 组合实现，每一步的中间结果都检查。align 与 page 为 0 或不是 2 的幂时返回 false（写进规格注释）。
  2. 验收表（在 64 位 size_t 的机器上）：
text
n=40       size=16  align=8   page=4096 -> bytes=640        pages=1
n=65536    size=16  align=16  page=4096 -> bytes=1048576    pages=256
n=3        size=5   align=8   page=4096 -> bytes=16         pages=1
n=SIZE_MAX/2 size=4 align=8   page=4096 -> false，乘法溢出
n=SIZE_MAX-2 size=1 align=8   page=4096 -> false，对齐加法溢出

第三行的 16 来自「15 字节按 8 对齐」。逐行打印 bytes 与 pages，对返回 false 的行打印失败原因编号（乘法溢出、对齐溢出、页数溢出）。

  1. mdr_alloc_round 对 bytes 为 0、1、4096、4097、0x40000000、0x80000000 各给出结果，并说明与 mdr_bit_ceil_u32 的关系。
  2. 写一条命令行小程序 alloc_plan n size align page，从 argv 读四个数，打印工具的输出。用 strtoull 读数时要检查转换错误与负数输入，说明为什么 (size_t)strtoull(...) 不能直接信任。
  3. 选做：把 mdr_alloc_plan 接进一个真实的分配包装 void *xmalloc(size_t n, size_t size)，要求乘法溢出时返回空指针而不是交给 malloc，并用 n = SIZE_MAX / 2、size = 4 演示不接检查时 malloc 会拿到什么参数。

9. 参考资料 ​