下個2的幂-一個簡單而優雅的算法優化介紹

在并行計算和圖形圖像等進行中，經常會遇到一類叫做"下個2的幂"的問題，簡單說來就是給定一個數，需要找到滿足如下條件的一個數：

最靠近這個數

大于或等于這個數

是2的n次方

簡單函數描述就是

<code>int nextpoweroftwo(int num);</code>

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

但明顯上述實作随着num的增大，時間就會成倍上升！

有沒有什麼好辦法呢？答案當然是：有

這裡給出了一個優雅的改進算法：

<a href="http://acius2.blogspot.com/2007/11/calculating-next-power-of-2.html">http://acius2.blogspot.com/2007/11/calculating-next-power-of-2.html</a>

下面是稍加改動後的一個實作

這個算法妙就妙在無論這個數多大，隻要進行5次右移并或的操作(32位)就夠了，堪稱精妙！

原理原文有述，簡單來說就是通過移位然後與原值進行或操作使得1的位成倍增加，因為是32位，是以重複進行5次1就覆寫了所有位（2的5次方），原例子不太直覺，這裡再舉個例子說明：

假設給定的數是65537，那麼

65537 - 1 = 65536

寫成二進制形式：

眼尖的同學對比下原文的例子可能會發現某些數（比如947這個數）并不需要循環5次1就已經占位滿了，這裡再貼下947的一個重複過程：

恩，在允許範圍内有部分數其實不需要重複完5次，我特别實驗了一下，比如在4096（可能還可以更大，有興趣同學可以進一步驗證下）範圍内，隻要重複4次就已經滿足要求！這有什麼意義呢，比如你給定的數能夠确定在某一個範圍，那完全可以減少重複次數！特别的，比如gl中紋理的尺寸一般不可能很大，這時就可以減少一次重複！5次減少一次，大約相當于減少五分之一！

上述算法通過取統計平均值計算耗時僅僅為開始算法的1/20左右！

這就結束了嗎？no

仔細觀察上述二進制串，可以發現如果能夠取到1之前的0的個數n，則通過1簡單的左移(32-n)就可以獲得想要的值，也就是1&lt;&lt;(32-n),這樣就可以一次就搞定！

這裡的關鍵是n怎麼取得，可以有很多算法來做這個事情，但上述我們已經優化到隻是幾次簡單的位操作，如果這裡取n再使用c算法算一遍，效率可能就要跪了！

恩，估計有同學想到了gcc中的一系列高效的built-in函數，__builtin_clz就可以用來取得1前面的0的個數,下面是簡單的實作：

上述算法通過取統計平均值計算耗時在前一算法的基礎上幾乎又提升了一倍！

這個算法前提是編譯器必須支援builtin函數,可以加一些編譯開關來獲得相容性平衡！

builtin函數介紹可以參看：

<a href="https://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/other-builtins.html">https://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/other-builtins.html</a>

比如開源浏覽器 mozilla firefox 源碼中就有這麼一個實作：

<a href="https://dxr.mozilla.org/mozilla-central/rev/aa90f482e16db77cdb7dea84564ea1cbd8f7f6b3/gfx/gl/gluploadhelpers.cpp">https://dxr.mozilla.org/mozilla-central/rev/aa90f482e16db77cdb7dea84564ea1cbd8f7f6b3/gfx/gl/gluploadhelpers.cpp</a>