數據結構——算法之（015）（ 求整數二進制表示中1的個數）

【申明：本文僅限於自我歸納總結和相互交流，有纰漏還望各位指出。 聯系郵箱：[email protected]】

題目：

輸入一個整數，求改整數的二進制表達式中有多少個1.例如輸入10，由於其二進制表示為1010，有兩個1，因此輸出2.

題目分析：

解法一、從右邊開始計算位為1的個數：用右移運算符，先判斷最右邊的那位是不是1，接著往右移一位。一直循環往復直到輸入的值變為0為止。

解法二、從左邊開始計算位為1的個數：另外一種思路是如果一個整數不為0，那麼這個整數至少有一位是1。如果我們把這個整數減去1，那麼原來處在整數最右邊的1就會變成0，原來在1後面的所有的0都會變成1。其余的所有位將不受到影響

算法實現：

#include 

/*
** 從最右邊開始計算位為1的個數
*/
int count_bit_1(int m)
{
    int count = 0;
    while(m)
    {
        if(m & 1)
            count++;
        m = m >> 1;
    }
    return count;
}

/*
** 從最左邊開始計算位為1的個數
*/
int count_bit_2(int m)
{
    int count = 0;
    while(m)
    {
        count++;
        m = (m - 1)&m;
    }
    return count;
}

int main(int argc, char *argv[])
{
    int m = atoi(argv[1]);
    printf("%d--method one--->%d\n", m, count_bit_1(m));
    printf("%d--method two--->%d\n", m, count_bit_2(m));
    return 0;
}