下个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的位数再翻倍

+1
0000 0000 0000 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次减少一次，大约相当于减少五分之一！

上述算法通过取统计平均值计算耗时仅仅为开始算法的1/20左右！

这就结束了吗？No

仔细观察上述二进制串，可以发现如果能够取到1之前的0的个数n，则通过1简单的左移(32-n)就可以获得想要的值，也就是1<<(32-n),这样就可以一次就搞定！
这里的关键是n怎么取得，可以有很多算法来做这个事情，但上述我们已经优化到只是几次简单的位操作，如果这里取n再使用c算法算一遍，效率可能就要跪了！

恩，估计有同学想到了gcc中的一系列高效的built-in函数，__builtin_clz就可以用来取得1前面的0的个数,下面是简单的实现：

int  nextPowerOfTwo(int num)
{
    return 1 << (32 - __builtin_clz(num - 1));    
}

上述算法通过取统计平均值计算耗时在前一算法的基础上几乎又提升了一倍！

这个算法前提是编译器必须支持builtin函数,可以加一些编译开关来获得兼容性平衡！
builtin函数介绍可以参看：
https://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/Other-Builtins.html

比如开源浏览器 mozilla FireFox 源码中就有这么一个实现：

https://dxr.mozilla.org/mozilla-central/rev/aa90f482e16db77cdb7dea84564ea1cbd8f7f6b3/gfx/gl/GLUploadHelpers.cpp

static int NextPowerOfTwo(int aNumber)
{
#if defined(__arm__)
    return 1 << (32 - __builtin_clz(aNumber - 1));
#else
    --aNumber;
    aNumber |= aNumber >> 1;
    aNumber |= aNumber >> 2;
    aNumber |= aNumber >> 4;
    aNumber |= aNumber >> 8;
    aNumber |= aNumber >> 16;
    return ++aNumber;
#endif
}