22、位操作与算法：用位运算实现下一个2的幂

各位做嵌入式开发的同行，今天我们来聊一个很实在的话题——用位运算找到下一个2的幂。

什么叫“下一个2的幂”？举个例子：你有一个数 5，下一个2的幂就是 8；你有 13，下一个就是 16；你有 32 本身，那下一个还是 32（有些场景要求严格大于，我们后面会区分）。

这个需求在嵌入式里太常见了。我做过一个内存池分配器，每次申请的内存块大小必须对齐到2的幂，否则内部碎片会搞得你头疼。还有做环形缓冲区、FFT 算法、哈希表扩容……几乎每个项目都会碰到。

你可能会说：“直接用循环乘2不就行了？”嗯，可以，但效率太低了。尤其在一些实时性要求高的场景，循环就是灾难。今天我就带你看看，怎么用纯位运算，几条指令搞定它。

22.1 核心思路：把最高位后面的所有位都填成1

我们先想清楚数学本质。

一个2的幂，二进制形式只有一个1。比如 8 是 1000，16 是 10000。

那对于一个任意数，比如 5（0101），它的下一个2的幂是 8（1000）。怎么从 0101 变到 1000？

我个人的习惯是这么理解的：先找到最高位的1，然后把所有低位都填成1，最后再加1。

你看：

• 5 的二进制：0101
• 最高位是第2位（从0开始数），把第2位后面的所有位都置1：0111 → 这是7
• 7 + 1 = 8 → 1000

完美。那问题就变成了：如何用位运算把最高位后面的所有位都变成1？

22.2 经典实现：32位无符号整数的解法

下面这段代码，是我在项目中用了十几年的版本。它来自《Hacker's Delight》这本书，但我在实际工程中做过微调。

// 计算下一个2的幂（对于32位无符号整数）
// 如果 n 本身就是2的幂，返回 n
unsigned int next_power_of_2(unsigned int n)
{
    // 先处理 n=0 的情况
    if (n == 0) return 1;

    // 减1是为了处理 n 本身就是2的幂的情况
    n--;

    // 把最高位后面的所有位都填成1
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    // 加1得到下一个2的幂
    return n + 1;
}

这段代码看起来有点“暴力”，但效率极高。我们来拆解一下。

22.2.1 为什么要先减1？

这是个细节，但很重要。我曾经在这个地方踩过坑。

假设 n 本身就是 8（1000）。如果不减1，直接做移位或运算：

• 1000 | 0100 = 1100
• 1100 | 0011 = 1111
• 最后 +1 → 10000，也就是 16

你看，8 的下一个2的幂变成了 16。但很多场景下，我们希望 8 本身就算一个2的幂，返回 8 就行。

所以先 n--，把 8 变成 7（0111），然后填1操作得到 0111，再加1得到 1000，正好是 8。完美。

22.2.2 移位或运算的“传染”过程

我们拿一个随机数来演示，比如 19（0001 0011）。

步骤	操作	结果
初始	n = 19	0001 0011
减1	n--	0001 0010
第1步	n |= n >> 1	0001 1011
第2步	n |= n >> 2	0001 1111
第3步	n |= n >> 4	0001 1111
第4步	n |= n >> 8	0001 1111
第5步	n |= n >> 16	0001 1111
加1	n + 1	0010 0000 = 32

你看，经过5次移位或运算，最高位后面的所有位都变成了1。这就是“传染”的效果——每次右移，都把高位的1往低位传播。

为什么是 1、2、4、8、16 这五个步长？因为 1+2+4+8+16 = 31，正好覆盖了32位整数的所有位。对于64位整数，你还需要再加一步 n |= n >> 32。

22.3 流程图：位运算填1的过程

下面我用一张 SVG 图来展示这个“传染”过程，方便你理解。

22.4 边界情况与避坑指南

代码写完了，但实际工程中坑不少。我一个个说。

22.4.1 n = 0 的情况

0 的下一个2的幂是什么？按定义，0 没有最高位的1，所以我们的算法会出问题。我习惯返回 1，因为 2^0 = 1。但有些场景可能要求返回 0，看你的业务。

22.4.2 溢出问题

对于 32 位无符号整数，最大的2的幂是 0x80000000（2^31）。如果你传入 0x80000000，减1后是 0x7FFFFFFF，填1后还是 0x7FFFFFFF，加1得到 0x80000000，没问题。

但如果你传入 0x80000001，减1后是 0x80000000，填1后变成 0xFFFFFFFF，加1变成 0——溢出了。所以这个算法对于大于 0x80000000 的数会返回 0。你需要根据业务决定是否要处理这种情况。

我曾经在一个网络协议栈里遇到过这个问题。当时分配缓冲区大小，用户传了一个接近 4G 的值，结果返回了 0，导致后续 memcpy 直接崩溃。排查了半天才发现是这里溢出了。

22.4.3 64位版本

如果你在 64 位系统上工作，代码稍微改一下：

unsigned long long next_power_of_2_64(unsigned long long n)
{
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n |= n >> 32;  // 多这一步
    return n + 1;
}

22.5 另一种思路：用内置函数

如果你用的是 GCC 或 Clang，可以用内置函数 __builtin_clz()（Count Leading Zeros）来快速找到最高位的位置。

unsigned int next_power_of_2_builtin(unsigned int n)
{
    if (n == 0) return 1;
    if (n && (n & (n - 1)) == 0) return n;  // 已经是2的幂
    return 1 << (32 - __builtin_clz(n));
}

这个写法更直观：先数前导0的个数，然后用 1 左移对应的位数。但 __builtin_clz(0) 是未定义行为，所以要先处理 n=0。

我个人更推荐前面那个移位或运算的版本，因为它不依赖编译器扩展，可移植性更好。你在 ARM、RISC-V、x86 上都能用，甚至在一些古老的编译器上也能跑。

22.6 实际应用场景

最后聊几个我遇到过的真实场景。

• 内存池对齐：做嵌入式内存池时，每个分配块的大小必须对齐到2的幂，否则内部碎片会浪费大量空间。用这个算法，每次分配时把请求大小“向上取整”到2的幂。
• 哈希表扩容：哈希表的容量通常保持为2的幂，这样可以用位运算代替取模。每次扩容时，新容量 = next_power_of_2(旧容量 * 2)。
• FFT 算法：快速傅里叶变换要求数据点数为2的幂。如果采集到的数据不是2的幂，就用这个算法补零到下一个2的幂。
• 环形缓冲区：缓冲区大小设为2的幂，可以用 index & (size - 1) 代替 index % size，效率高很多。

好了，关于用位运算实现下一个2的幂，核心内容就这些。记住那个“减1、填1、加1”的三步曲，以后遇到类似需求，你就能信手拈来了。

---

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