劍指offer筆記——面試題15：二進制中1的個數

• 問題描述
• 代碼
• 運作結果
• 相關題目

問題描述

請實作一個函數，輸入一個整數，輸出該數二進制表示中1的個數。

代碼

#include <iostream>

/**
 * 求一個整數的二進制中1的個數
 * 正常解法，循環的次數等于整數二進制的位數，32位的整數需要循環32次
 */
int NumberOf1_1(int n)
{
    int count = 0;
    unsigned int flag = 1;
/*
    起初看書的時候我還以為會陷入死循環，運作時發現flag增加到2147483648後再次左移會變成0進而結束循環
    這是我對資料類型的知識了解不夠
    雖然不會陷入死循環，但這樣無論幾位的數也要循環32次，是以可以先對變量n的位數先做一個判斷
    int digitCount = 0;
    for(int m = n; m != 0; m = m >> 1,digitCount++)
        ;
    但是這樣的方法不能用于負數，是以程式還是使用書中的寫法
*/
    for(; flag;)
    {
        if(n & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}
/**
 * 求一個整數的二進制中1的個數
 * 能給面試官帶來驚喜的解法，循環的次數等于整數的二進制中1的個數
 */
int NumberOf1_2(int n)
{
    int count = 0;
    for(; n;)
    {
        count++;
        n = (n - 1) & n;    // 這樣計算的效果是，把整數的二進制中，最右邊的1，變成0
    }
    return count;
}
int main()
{
    std::cout << NumberOf1_1(9) << std::endl;
    std::cout << NumberOf1_2(9) << std::endl;
    std::cout << NumberOf1_1(-9) << std::endl;
    std::cout << NumberOf1_2(-9) << std::endl;
    std::cout << NumberOf1_1(0) << std::endl;
    std::cout << NumberOf1_2(0) << std::endl;
    return 0;
}

           

運作結果

相關題目

• 用一條語句判斷一個整數是不是2的整數次方。

一個整數如果是2的整數次方，那麼它的二進制表示中有且隻有一位是1，而其他所有位都是0。根據前面的分析，把這個整數減去1之後再和它自己做與運算，這個整數中唯一的1就會變成0

• 輸入兩個整數m和n，計算需要改變m的二進制表示中的多少位才能得到n。比如10的二進制表示為1010，13的二進制表示為1101，需要改變1010中的3位才能得到1101

我們可以分為兩步解決這個問題：第一步求這兩個數的異或；第二步統計異或結果中1的位數