用 O(1) 時(shí)間檢測(cè)整數(shù) n 是否是 2 的冪次。
樣例
n=4，返回 true;
n=5，返回 false.
除以2
這個(gè)當(dāng)然是很簡(jiǎn)單也最容易想到，int的話可能要除31次才能出來。
統(tǒng)計(jì)1的位數(shù)
這個(gè)也容易想到，如果是2的冪次的話肯定是正的，然后去統(tǒng)計(jì)1的個(gè)數(shù)，需要移位和取且操作，和上面的方法差不多。因?yàn)槌?本來就可以通過移位操作完成。
bool checkPowerOf2(int n) {
int num=0;
for(int i=0;i<31;i++)
{
if((n>>i)&1==1)
{
num++;
}
}
return num==1;
// write your code here
}
n和n-1取且
這個(gè)是以前檢測(cè)有多少個(gè)1的時(shí)候用到的一種方法，那個(gè)時(shí)候有一個(gè)結(jié)論：n&n-1可以減少一位1,如果用這種方法，那代碼是相當(dāng)簡(jiǎn)單：也符合時(shí)間復(fù)雜度要求。
bool checkPowerOf2(int n) {
if(n<=0)
return false;
return !(n&(n-1));
// write your code here
}
還有復(fù)習(xí)一下計(jì)算機(jī)中數(shù)字的表達(dá)形式：
- 有符號(hào)數(shù)最高位做符號(hào)位，0為正，1為負(fù)。
- 正數(shù)就是按照正常的表示方法。
- 負(fù)數(shù)用補(bǔ)碼表示，補(bǔ)碼為反碼加1，反碼是除符號(hào)位外其他位逐位取反。
- -0表示當(dāng)前位數(shù)最小的那個(gè)數(shù)。
- n位有符號(hào)數(shù)的表示范圍： -2^n-- 2^(n-1)-1
原碼的表示：
左邊是符號(hào)位，正數(shù)為0，負(fù)數(shù)為1。其他位表示數(shù)值
【+10】原碼 = 00001010
【-10】原碼 = 10001010
【+0】原碼 = 00000000
【-0】原碼 = 10000000
反碼的表示：
正數(shù)的反碼和原碼相同，負(fù)數(shù)的反碼由原碼除了符號(hào)位的其余位取反（即0表1,1表0）
【+10】反碼 = 00001010
【-10】反碼 = 11110101
【+0】反碼 = 00000000
【-0】反碼 = 11111111
補(bǔ)碼的表示：
正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)的補(bǔ)碼由原碼的反碼加1得到
【+10】補(bǔ)碼 = 00001010
【-10】補(bǔ)碼 = 【-10】反碼 + 1 = 11110101 + 1 = 11110110
【+0】補(bǔ)碼 = 00000000
【-0】補(bǔ)碼 = 【-0】反碼 + 1 = 11111111 + 1 = 【1】00000000（mod（256））
補(bǔ)碼的意義：補(bǔ)碼實(shí)際上是一種模運(yùn)算，以時(shí)鐘為例，時(shí)鐘一圈是12個(gè)小時(shí)，即時(shí)鐘的模為12。如果當(dāng)前時(shí)刻是3點(diǎn)鐘，在12個(gè)小時(shí)之后時(shí)刻變?yōu)?5點(diǎn)，15在模12之后，依然是3點(diǎn)。再如，將3點(diǎn)的時(shí)針調(diào)慢一個(gè)小時(shí)，即調(diào)成2點(diǎn)，和將時(shí)針向前調(diào)整11個(gè)小時(shí)的效果是一樣的。因此用3-1和（3+11）mod（12）的結(jié)果一樣。補(bǔ)碼在機(jī)器碼中的運(yùn)用主要是用加法元算代替減法運(yùn)算。CPU的加法器簡(jiǎn)單效率高，因此不需要再專門實(shí)現(xiàn)減法器。
在8位字中，我們的模就是2的8次方，即256。例如：
直接減法：01000000（64）— 00001010（10） = 00110110（54）
用補(bǔ)碼代替減法：01000000（64）+（11110110）（246）= 00110110（54）
兩種運(yùn)算結(jié)果是一樣的。
