20、位操作与算法：用位运算实现后导零计数（ctz）

后导零计数，英文叫 Count Trailing Zeros，简称 ctz。说白了，就是给一个整数，从最低位（LSB）开始往高位数，看连续有多少个 0。比如数字 8（二进制 1000），后导零就是 3；数字 6（二进制 0110），后导零就是 1。

这个操作在底层开发里非常常见。我做过一个嵌入式实时系统，里面有个调度器需要快速找到就绪队列中优先级最高的任务。那个就绪队列是用位图表示的，每次调度都要做 ctz。如果不用位运算硬算，性能根本扛不住。

20.1 为什么需要 ctz？

你想想看，在很多场景下，我们都需要快速定位到最低位的 1。比如：

• 位图调度器：找到最低优先级的就绪任务
• 哈夫曼编码：快速找到编码树中的叶子节点
• 循环缓冲区：计算当前写指针到下一个对齐地址的距离
• 二分查找：某些变种算法需要快速定位分界点

这些场景如果用循环一位一位地检查，效率太低了。尤其是嵌入式系统里，CPU 主频本来就低，能省一个周期是一个周期。

20.2 朴素实现：逐位检查

先看一个最直接的写法。我刚入行时也这么写过，后来被老工程师骂了一顿——太慢了。

int ctz_naive(uint32_t x) {
    if (x == 0) return 32;  // 特殊处理
    int count = 0;
    while ((x & 1) == 0) {
        count++;
        x >>= 1;
    }
    return count;
}

这个代码的问题很明显：如果后导零很多，循环次数就多。最坏情况要循环 31 次。在实时系统里，这种不确定的执行时间是很危险的。

20.3 二分法：用分治思想加速

既然逐位检查太慢，那能不能用二分法？当然可以。这个思路我在一个网络协议栈的 CRC 计算模块里用过，效果很好。

核心思想：先判断低 16 位是否全为 0，如果是，说明后导零至少 16 个，然后继续判断高 16 位；如果不是，说明后导零在低 16 位里，继续二分。

int ctz_binary(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
    if ((x & 0x000000FF) == 0) { n += 8;  x >>= 8;  }
    if ((x & 0x0000000F) == 0) { n += 4;  x >>= 4;  }
    if ((x & 0x00000003) == 0) { n += 2;  x >>= 2;  }
    if ((x & 0x00000001) == 0) { n += 1;             }
    return n;
}

这个版本最多只需要 5 次判断，比循环快多了。而且没有分支预测失败的问题——每个 if 都是独立的，CPU 可以并行执行。

20.4 查表法：空间换时间

还有一种经典做法是查表。把 8 位或 16 位的所有可能值对应的 ctz 结果预先算好，存到数组里。运行时直接查表。

static const uint8_t ctz_table[256] = {
    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

int ctz_table(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF) == 0) { n += 16; x >>= 16; }
    if ((x & 0x00FF) == 0) { n += 8;  x >>= 8;  }
    return n + ctz_table[x & 0xFF];
}

这个版本只需要 256 字节的表，在大多数 MCU 上都能接受。查表法的好处是执行时间完全确定，没有分支预测的烦恼。

20.5 德布罗意序列：最优雅的解法

如果你追求极致性能，可以试试德布罗意序列（De Bruijn sequence）。这个技巧我在一个加密算法优化项目里用过，当时把 ctz 从 12 个周期降到了 3 个周期。

原理很简单：用一个特殊的 32 位常数，把最低位 1 的位置映射到一个唯一的 5 位索引，然后查一个 32 字节的小表。

static const uint8_t ctz_debruijn[32] = {
    0,  1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

int ctz_debruijn(uint32_t x) {
    if (x == 0) return 32;
    // 提取最低位的 1
    uint32_t lsb = x & (-x);
    // 用德布罗意序列映射
    uint32_t hash = (lsb * 0x077CB531U) >> 27;
    return ctz_debruijn[hash];
}

这里的关键是 x & (-x)，它提取出最低位的 1。然后乘以一个精心挑选的常数，得到一个唯一的哈希值。这个哈希值正好落在 0~31 之间，查表即得结果。

20.6 各方法对比

我把这几种方法在 Cortex-M4 上实测过，结果如下：

我个人最常用的是二分法。它不需要额外的 RAM，代码量也小，性能足够。只有在性能瓶颈非常明显时，我才会换成德布罗意序列。

20.7 避坑指南

我曾经在一个项目里吃过亏，分享出来给大家提个醒：

• 输入为 0 的处理：ctz(0) 的结果在不同 CPU 上不一样。x86 的 BSF 指令在输入为 0 时，ZF 置位，结果未定义。TZCNT 指令则返回 32。写跨平台代码时一定要统一处理。
• 有符号数的陷阱：如果你传入了负数，x & (-x) 的行为是定义良好的，但结果可能不是你想要的。建议统一用无符号类型。
• 编译器优化：GCC 的 __builtin_ctz 在输入为 0 时是未定义行为。Clang 则返回 32。不要依赖编译器的具体实现。

20.8 知识体系图

下面这张图总结了 ctz 的几种实现方法和它们之间的关系：

20.9 总结

ctz 这个操作看似简单，但实现方式多种多样。从最朴素的循环，到二分法，再到查表法和德布罗意序列，每种方法都有自己的适用场景。

我个人的建议是：

• 如果你在写通用库，用二分法，它足够快且不占额外内存。
• 如果你在写性能敏感的代码（比如调度器、加密算法），用德布罗意序列。
• 如果你在写裸机代码，RAM 很充裕，用查表法。

嗯，ctz 就讲到这里。记住一点：位操作的精髓不在于炫技，而在于用最少的资源解决问题。下次遇到需要数后导零的场景，你应该知道怎么选了。

公众号:蓝海资料掘金营，微信deep3321