第22章二进制位数组

按SDS字节和大端位序解释GETBIT、SETBIT、查表与SWAR BITCOUNT以及BITOP 覆盖7个正式节点，并以Redis 3.0源码、故障和恢复对账验收。

学习目标

能说明位数组与字符串的关系
能使用 SETBIT/GETBIT/BITCOUNT
能用 BITOP 做集合式位运算

为什么从“位偏移与BITCOUNT算法台”开始

第22章二进制位数组的核心任务是按SDS字节和大端位序解释GETBIT、SETBIT、查表与SWAR BITCOUNT以及BITOP。命令返回值只暴露外层合同；实现解释还必须连接内存结构、写入与读取路径、事件顺序以及失败后的旧状态回收。位偏移与BITCOUNT算法台把这些关系放进同一条可复位轨迹。

先写预测：当位偏移由“跨字节”进入“扩展尾部”时，哪个可观察状态最先变化？再规定什么结果会推翻当前解释。交互中的分数只表达透明因果方向，不冒充真实Redis测量。

来源、版次与独立重写边界

黄健宏作者读者服务页确认正式出版新版以Redis 3.0为源码基线，列出4部分、24章及完整小节，并链接Redis 3.0中文注释源码。本课程据此映射24个正式单元、145个目录节点，另设学习地图和总复习；未取得出版正文授权，目录只界定范围，不宣称复现原书正文。

本章字段与控制流由Redis官方3.0源码：bitops.c和作者注释源码交叉核对；Redis当前持久化文档只用于辨认版本差异。中文解释、图示、交互、实验与答案均为独立教学重写，不把目录页或代码仓库许可证误报为原书许可证。

本章术语与源码合同

第22章二进制位数组必须守住“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”。观察同时记录位偏移与BITCOUNT算法台一致率与运算分叉风险；只有结构快照、函数入口、运行结果和故障反例互相一致，才接受实现结论。

⚡ 内存淘汰策略：LRU / LFU

Redis 的近似 LRU 通过采样淘汰（eviction-pool）替代全量排序，性能远优于严格 LRU。LFU 使用莫里斯计数器（概率计数器）近似记录访问频率，节省内存。maxmemory-policy 还支持 volatile-TTL / allkeys-random / noeviction 等策略。

操作日志

1.内存淘汰：maxmemory 策略包含 LRU（最近最少使用）与 LFU（最不常使用）。

作者目录逐项深读

位数组的表示

四级证据 1/7。 Redis把字符串SDS作为字节数组，位偏移先定位字节再按高位优先映射位，越界读取返回0。本节点用“位数组的表示”作观察点，执行rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证位数组的表示时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

GETBIT命令的实现

四级证据 2/7。 GETBIT计算byte=offset/8与bit=7-offset%8，字符串之外的偏移读取为0且不扩展值。本节点用“GETBIT命令的实现”作观察点，执行rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证GETBIT命令的实现时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

SETBIT命令的实现

四级证据 3/7。 SETBIT必要时扩展字符串并补零，按掩码修改目标位并返回旧位值。本节点用“SETBIT命令的实现”作观察点，执行rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证SETBIT命令的实现时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

BITCOUNT命令的实现

四级证据 4/7。 BITCOUNT对短输入可查表，对长输入可用SWAR并处理头尾未对齐字节，结果应与逐位计数一致。本节点用“BITCOUNT命令的实现”作观察点，执行rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证BITCOUNT命令的实现时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

BITOP命令的实现

四级证据 5/7。 BITOP按字节执行AND、OR、XOR或NOT；不同长度输入的缺失尾部按零处理并写入目标键。本节点用“BITOP命令的实现”作观察点，执行rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证BITOP命令的实现时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

重点回顾

四级证据 6/7。 第22章二进制位数组的回顾要重新证明“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，并用同一输入比较结构前态、变更轨迹、故障首错与恢复后态

验证重点回顾时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

参考资料

四级证据 7/7。 本章目录范围由作者页面确认，字段和控制流回到Redis 3.0的bitops.c与黄健宏注释源码核验；新版资料只承担差异说明

验证参考资料时，先预测位偏移从“跨字节”切到“扩展尾部”会改变哪个字段、偏移、文件或消息；再固定运算做一次对照。若故障注入没有破坏“偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致”，就撤回当前解释而不是补写故事。

最小源码与运行切片

+git clone --branch 3.0 --depth 1 https://github.com/redis/redis.git redis-3.0
+cd redis-3.0
+rg 'getbitCommand|setbitCommand|bitcountCommand|bitopCommand' src/bitops.c

该切片固定Redis 3.0分支、编译器、配置、数据集和命令序列；先保存结构或函数位置，再运行隔离实例。任何持久化损坏、断线、故障转移、大键或高流量实验都必须使用临时数据并规定CPU、内存、磁盘、延迟和停止上限。

unit: rdi-22-bit-array
source_file: bitops.c
axis_a: "位偏移"
axis_b: "运算"
fault: "按本机位序而非Redis定义映射偏移，造成SETBIT与BITCOUNT结果不一致"
invariant: "偏移到字节与位的映射正确，扩展补零，计数和按位运算对任意长度输入一致"
replay: same_version_same_input

三个必须主动触发的误区

误区 1

现象 → 偏移量随意取大值 原因 → 单次分配整块内存 修法 → 按用户段分键控制大小

误区 2

现象 → 位图当日志追加 原因 → 位图无序不可遍历 修法 → 日志用 List/Stream

误区 3

现象 → BITCOUNT 全图频繁算 原因 → 大图统计耗时 修法 → 用计数缓存或分段统计

小结

位数组用字符串承载位操作
SETBIT/GETBIT 操作单个位
BITCOUNT 统计置位数量
BITOP 做位逻辑组合
适合签到与布隆类场景

练习、答案与节点验证

练习

问题 1： 位图相比布尔数组省多少内存？

问题 2： BITOP 的典型应用场景？

问题 3： 用位图实现 7 天连续签到统计。（独立实现）

术语复核与本章回顾

完成第22章二进制位数组意味着能从bitops.c解释按SDS字节和大端位序解释GETBIT、SETBIT、查表与SWAR BITCOUNT以及BITOP，能运行章专属状态实验，能制造反例并在复位后证明旧状态没有残留。