問(wèn)題來(lái)源：Power of Two
即判斷一個(gè)整數(shù)是否為2的冪，注意這里的整數(shù)有可能是負(fù)整數(shù)，某些針對(duì)正整數(shù)的算法并不適用。以下是幾種通過(guò)了測(cè)試的代碼（C語(yǔ)言）以及在leetcode上測(cè)試1108個(gè)用例花費(fèi)的時(shí)間。
- 除法
不斷對(duì)輸入的整數(shù)做除法，如果最后的商是1，那么這個(gè)整數(shù)是2的冪；如果商在變?yōu)?之前已經(jīng)是一個(gè)奇數(shù)（如7/2為3），那么這個(gè)整數(shù)不是2的冪。代碼如下：
bool isPowerOfTwo(int n) {
while ((n % 2 == 0) && n > 1)
n /= 2;
return (n == 1);
}
耗時(shí)4ms。 - 右移
這種算法和除法是相等的，除以2實(shí)際上相當(dāng)于右移 1 bit，檢查一個(gè)二進(jìn)制數(shù)是否為奇數(shù)和檢查它的最后一位是否為 1 相同。代碼如下：
bool isPowerOfTwo(int n) {
while (((n & 1) == 0) && n > 1) /* While n is even and > 1 /
n >>= 1;
return (n == 1);
}
耗時(shí)同樣為4ms。
3.數(shù)“1”
這種想法最為自然，因?yàn)?的冪表示為二進(jìn)制都是1后面加上相應(yīng)數(shù)量的0（如32的二進(jìn)制表示為100000），如果二進(jìn)制里出現(xiàn)了多于一個(gè)的“1”這個(gè)整數(shù)一定不是2的冪。代碼如下：
bool isPowerOfTwo(int x) {
unsigned int numberOfOneBits = 0;
while(x && numberOfOneBits <=1)
{
if ((x & 1) == 1) / Is the least significant bit a 1? /
numberOfOneBits++;
x >>= 1; / Shift number one bit to the right /
}
return (numberOfOneBits == 1); / 'True' if only one 1 bit */
}
耗時(shí)8ms。
參考資料：Ten Ways to Check if an Integer Is a Power Of Two in C
