下个2的幂：一个简单而优雅的算法优化介绍

在并行计算和图形图像等处理中，经常会遇到一类叫做"下个2的幂"的问题，简单说来就是给定一个数，需要找到满足如下条件的一个数：
1. 最靠近这个数 
2. 大于或等于这个数 
3. 是2的N次方

简单函数描述就是
int nextPowerOfTwo(int num);

首先想到的一般算法可能是：

 int nextPowerOfTwo(int num)
 { int npot = 1; while( npot < num ) npot <<= 1; return npot;      
 } 

但明显上述实现随着num的增大，时间就会成倍上升！

有没有什么好办法呢？答案当然是：有

这里给出了一个优雅的改进算法：
http://acius2.blogspot.com/2007/11/calculating-next-power-of-2.html

下面是稍加改动后的一个实现

int nextPowerOfTwo(int num)
{ if (0 == num--) return 1;
    } num = (num >> 1) | num; num = (num >> 2) | num; num = (num >> 4) | num; num = (num >> 8) | num; num = (num >> 16) | num; //num = (num >> 32) | num;//如果是64位机器则需要增加一次计算 return ++num;           
} 

这个算法妙就妙在无论这个数多大，只要进行5次右移并或的操作(32位)就够了，堪称精妙！
原理原文有述，简单来说就是通过移位然后与原值进行或操作使得1的位成倍增加，因为是32位，所以重复进行5次1就覆盖了所有位（2的5次方），原例子不太直观，这里再举个例子说明：

假设给定的数是65537，那么
65537 - 1 = 65536
写成二进制形式：

0000 0000 0000 0001 0000 0000 0000 0000 1 0000 0000 0000 0000 1000 0000 0000 0000 //右移1位 0000 0000 0000 0001 1000 0000 0000 0000 //与原值或 ，1的位数翻倍 2 0000 0000 0000 0000 0110 0000 0000 0000 //右移2位 0000 0000 0000 0001 1110 0000 0000 0000 //与原值或，1的位数再翻倍 3 0000 0000 0000 0000 0001 1110 0000 0000 //右移4位 0000 0000 0000 0001 1111 1110 0000 0000 //与原值或，1的位数再翻倍 4 0000 0000 0000 0000 0000 0001 1111 1110 //右移8位 0000 0000 0000 0001 1111 1111 1111 1110 //与原值或，1的位数再翻倍 5 0000 0000 0000 0000 0000 0000 0000 0001 //右移16位 0000 0000 0000 0001 1111 1111 1111 1111 //与原值或，1的位数再翻倍 [phone] 0010 0000 0000 0000 0000 // 131072 

眼尖的同学对比下原文的例子可能会发现某些数（比如947这个数）并不需要循环5次1就已经占位满了，这里再贴下947的一个重复过程：

0000 0011 1011 0011 0000 0011 1111 1011 0000 0011 1111 1111 //...with the remaining steps staying at this value. 

恩，在允许范围内有部分数其实不需要重复完5次，我特别实验了一下，比如在4096（可能还可以更大，有兴趣同学可以进一步验证下）范围内，只要重复4次就已经满足要求！这有什么意义呢，比如你给定的数能够确定在某一个范围，那完全可以减少重复次数！特别的，比如GL中纹理的尺寸一般不可能很大，这时就可以减少一次重复！5次减少一次，大约相当于减少五分之一！

阅读全文请点击：