29、位操作与算法：用位运算实现整数对数

说到对数，大家第一反应可能是数学库里的 log() 函数。但在嵌入式世界里，很多时候我们不需要浮点运算，也不方便调用数学库。我做过不少通信协议栈和传感器数据处理的项目，经常需要估算一个整数的量级——说白了，就是想知道这个数大概有多大，用二进制表示的话占多少位。

这个需求，其实就是整数对数。具体来说，就是求 floor(log2(n))，也就是以2为底的对数向下取整。比如 log2(8) = 3，log2(10) = 3（因为 2³=8，2⁴=16，10 在中间）。

用位运算实现整数对数，核心思路只有一个：找到最高位的1所在的位置。你想想看，一个整数的二进制表示中，最高位的1在第几位，这个数就落在 2^(k) 到 2^(k+1)-1 之间，那它的整数对数就是 k。

方法一：逐位右移法

最直观的方法，就是不断右移，数一数要移多少次才能把数变成0。这个方法简单，但效率一般。

int int_log2_shift(uint32_t x) {
    int result = -1;
    while (x > 0) {
        x >>= 1;
        result++;
    }
    return result;
}

嗯，这里要注意：如果 x 是0，返回 -1 表示未定义。我在实际项目中一般会先判断一下输入是否为0。

这个方法的复杂度是 O(n)，n 是整数的位数。对于32位整数，最多循环32次。说实话，在大多数场景下够用了。但我曾经在一个音频采样率转换的算法里用过这个，每次处理几千个样本，每个样本都要算一次对数，32次循环就变成了几万次操作——这时候就得优化了。

方法二：二分查找法

既然我们要找最高位的1，那完全可以用二分法来加速。思路是：先看高16位有没有1，如果有，结果至少是16；再看高8位……以此类推。

int int_log2_binary(uint32_t x) {
    int result = 0;
    if (x >= 0x10000) { result += 16; x >>= 16; }
    if (x >= 0x100)   { result += 8;  x >>= 8;  }
    if (x >= 0x10)    { result += 4;  x >>= 4;  }
    if (x >= 0x4)     { result += 2;  x >>= 2;  }
    if (x >= 0x2)     { result += 1;  x >>= 1;  }
    return result;
}

这个写法很经典，固定5次判断，不管输入是多少。我特别喜欢这种「确定性执行时间」的算法，在实时系统里特别有用。你想想看，如果每个中断处理的时间都不一样，调度起来多麻烦。

方法三：查表法

如果空间换时间，查表法是最快的。但直接查32位整数的表需要4GB内存，显然不现实。所以一般用「分段查表」：先通过二分法缩小到8位或4位，再查小表。

static const uint8_t log2_table[256] = {
    0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
    // ... 省略中间数据，完整表需要256个条目
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

int int_log2_lut(uint32_t x) {
    int result = 0;
    if (x >= 0x10000) { result += 16; x >>= 16; }
    if (x >= 0x100)   { result += 8;  x >>= 8;  }
    return result + log2_table[x];
}

这个写法只需要256字节的表，加上两次判断，速度非常快。我曾经在一个电池管理系统的固件里用过这个，每次ADC采样后要快速计算电量百分比，查表法比逐位移法快了将近10倍。

方法四：内置指令法

如果编译器支持，可以用内置函数。GCC 和 Clang 都提供了 __builtin_clz()（Count Leading Zeros），直接返回前导零的个数。整数对数就是 31 - clz（对于32位整数）。

int int_log2_builtin(uint32_t x) {
    return 31 - __builtin_clz(x);
}

这个函数在底层会被编译成一条 CPU 指令（比如 ARM 的 CLZ 指令，x86 的 BSR 指令），效率最高。但要注意：__builtin_clz(0) 的行为是未定义的，需要先处理 x=0 的情况。

方法对比

方法	速度	代码大小	适用场景
逐位右移	慢（O(n)）	极小	教学、偶尔调用
二分查找	快（固定5步）	小	通用、实时系统
查表法	极快	中等（256字节）	高频调用、资源充足
内置指令	最快（1条指令）	极小	平台确定、性能敏感

实际应用场景

整数对数在嵌入式里用得挺多的。我随便列几个：

• 位图索引：用对数确定数据落在哪个桶里
• FIFO 深度计算：根据数据量估算需要的缓冲区大小
• 音频/图像量化：确定动态范围，做非线性映射
• 协议解析：解析变长编码时，快速知道数据长度

我记得有一次做 LoRa 网关的固件，需要根据信号强度快速估算距离。信号强度是 dBm 值，但底层 ADC 读出来的是原始值。用整数对数把原始值映射到对数域，再查表转成距离，整个过程没有用一次浮点运算，跑得飞快。

SVG 知识结构图

好了，整数对数这个看似简单的问题，用位运算实现起来其实有好几条路。关键是要理解它的本质——找最高位的1。理解了这一点，不管用哪种方法，你都能写出高效、可靠的代码。

---

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