題目：輸入一個整數(shù)，求該整數(shù)的二進制表達中有多少個1。例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。
分析：這是一道很基本的考查位運算的面試題。包括微軟在內(nèi)的很多公司都曾采用過這道題。
一個很基本的想法是，我們先判斷整數(shù)的最右邊一位是不是1。接著把整數(shù)右移一位，原來處于右邊第二位的數(shù)字現(xiàn)在被移到第一位了，再判斷是不是1。這樣每次移動一位，直到這個整數(shù)變成0為止�，F(xiàn)在的問題變成怎樣判斷一個整數(shù)的最右邊一位是不是1了。很簡單，如果它和整數(shù)1作與運算。由于1除了最右邊一位以外，其他所有位都為0。因此如果與運算的結(jié)果為1，表示整數(shù)的最右邊一位是1，否則是0。
得到的代碼如下：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution1(int i)
{
int count = 0;
while(i)
{
if(i & 1)
count ++;
i = i >> 1;
}
return count;
}
可能有讀者會問，整數(shù)右移一位在數(shù)學上是和除以2是等價的。那可不可以把上面的代碼中的右移運算符換成除以2呢?答案是不要換成除法。因為除法的效率比移位運算要低的多，在實際編程中如果可以應(yīng)盡可能地用移位運算符代替乘除法。
這個思路當輸入i是正數(shù)時沒有問題，但當輸入的i是一個負數(shù)時，不但不能得到正確的1的個數(shù)，還將導(dǎo)致死循環(huán)。以負數(shù)0x80000000為例，右移一位的時候，并不是簡單地把位的1移到第二位變成0x40000000，而是0xC0000000。這是因為移位前是個負數(shù)，仍然要保證移位后是個負數(shù)，因此移位后的位會設(shè)為1。如果一直做右移運算，最終這個數(shù)字就會變成0xFFFFFFFF而陷入死循環(huán)。
為了避免死循環(huán)，我們可以不右移輸入的數(shù)字i。首先i和1做與運算，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1……這樣反復(fù)左移，每次都能判斷i的其中一位是不是1�；诖耍覀兊玫饺缦麓a：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution2(int i)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(i & flag)
count ++;
flag = flag << 1;
}
return count;
}
另外一種思路是如果一個整數(shù)不為0，那么這個整數(shù)至少有一位是1。如果我們把這個整數(shù)減去1，那么原來處在整數(shù)最右邊的1就會變成0，原來在1后面的所有的0都會變成1。其余的所有位將不受到影響。舉個例子：一個二進制數(shù)1100，從右邊數(shù)起的第三位是處于最右邊的一個1。減去1后，第三位變成0，它后面的兩位0變成1，而前面的1保持不變，因此得到結(jié)果是1011。
我們發(fā)現(xiàn)減1的結(jié)果是把從最右邊一個1開始的所有位都取反了。這個時候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運算，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000。也就是說，把一個整數(shù)減去1，再和原整數(shù)做與運算，會把該整數(shù)最右邊一個1變成0。那么一個整數(shù)的二進制有多少個1，就可以進行多少次這樣的操作。
這種思路對應(yīng)的代碼如下：
///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution3(int i)
{
int count = 0;
while (i)
{
++ count;
i = (i - 1) & i;
}
return count;
}
跳臺階問題
題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。
分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。
首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級;另外一種就是一次跳2級。
現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1);另外一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下的n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。
我們把上面的分析用一個公式總結(jié)如下：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到這里，相信很多人都能看出這就是我們熟悉的Fibonacci序列。至于怎么求這個序列的第n項，請參考本面試題系列第16題，這里就不在贅述了。
