一個數(shù)的二進(jìn)制表示中1的個數(shù)——10

    實現(xiàn)一個函數(shù)，輸入一個整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個數(shù)。例如，將9表示成二進(jìn)制為1001，有2位是1，因此如果輸入數(shù)字9，該函數(shù)輸出2。

    如果讓我們將一個十進(jìn)制的數(shù)轉(zhuǎn)換成二進(jìn)制的表示，我們就會不停的模除模除2取它的余數(shù)，因此，就可以用這樣的方法解決：

#include <iostream>
using namespace std;

size_t count_one_num(int n)
{
    size_t count = 0;

    while(n != 0)
    {   
        if((n % 2) == 1)
            count++;
        n /= 2;
    }   
    return count;
}

int main()
{
    int n = 7;
    size_t ret = count_one_num(n);
    cout<<"one number in "<<n<<" are: "<<ret<<endl;

    return 0;
}

運(yùn)行程序：

    我們知道，任何一個數(shù)用機(jī)器語言來表示都是0和1的組合，而C/C++中提供了這樣的一個運(yùn)算符，右移操作符“>>”和左移操作符“<<”，它們是將一個數(shù)的二進(jìn)制位進(jìn)行相應(yīng)的向左移位和向右移位，而在上面的問題中，可以不斷地將整數(shù)向右進(jìn)行移位，這樣取到其最低位的數(shù)字和1數(shù)字進(jìn)行相與，就能夠得知最低位上的數(shù)字是1還是0了；

    但是提到移位操作符會存在一個問題，當(dāng)將一個數(shù)進(jìn)行左移時，左邊的位會被丟棄，而右邊的位會補(bǔ)0；當(dāng)一個數(shù)進(jìn)行右移操作時，右邊的位會被丟棄，那么左邊的補(bǔ)位會存在兩種情況：一種是邏輯移位，統(tǒng)一都補(bǔ)0；另一種是算數(shù)移位，會相應(yīng)的補(bǔ)符號位；因此，在設(shè)計循環(huán)判斷條件的時候，不能將判斷數(shù)字是否為0作為循環(huán)條件了，而是應(yīng)當(dāng)將整數(shù)的位數(shù)也就是32位作為循環(huán)終止的條件，程序如下：

size_t count_one_num(int n)
{
    int i = 32; 
    size_t count = 0;
    while(--i)
    {   
        if((n & 1) == 1)
            ++count;
        n = n>>1;
    }   
    return count;
}

    除了上面的方法，其實還有一種利用數(shù)字的二進(jìn)制來解決的辦法：可以想到，當(dāng)一個數(shù)不為0的時候，它的二進(jìn)制表示中至少有一個1，從而計數(shù)器就可以加1，然后就需要將二進(jìn)制中的1一個一個地剔除掉直到數(shù)字變?yōu)?，那除了移位怎樣才能辦到呢？可以將數(shù)字 =（數(shù)字）&（數(shù)字-1），因為一個數(shù)字減1的時候，它最低位的一個1就會變成0，而最低位的1肯定都是0就會都變成1，也就相當(dāng)于將數(shù)字12的二進(jìn)制減1就為將1100減1變成了1011值為11，然后將1100和1011進(jìn)行相&，那么就會變成1000，也就是成功的將12中的兩個1變成了一個1，以此類推就可以統(tǒng)計出二進(jìn)制中1的個數(shù)了，代碼實現(xiàn)如下：

size_t count_one_num(int n)
{
    size_t count = 0;
    while(n != 0)
    {   
        ++count;
        n = n & (n-1);
    }   
    return count;
}

這樣的代碼是不是比前兩種更簡潔直觀呢，只是在理解上要稍微轉(zhuǎn)一下彎。

《完》