劍指offer之二進制中1的個數

1 問題

實作一個函數，輸入一個函數，輸出該二進制資料中1的個數。例如9表示二進制資料1001，有2位是1，是以輸入9，該函數會輸出2。

2 分析

我們先了解下計算機裡面位運算，有5種

1）& 這個是與操作，規律如下

1 & 1 = 1     1 & 0 = 0     0 & 1= 0    0 & 0 = 0

2）| 這個是或運算，規律如下

1 | 1 = 1     1 | 0 = 1     0 | 1= 1    0 | 0 = 0

3）^ 異或運算，規律如下

1 ^ 1 = 0     1 ^ 0 = 1      0 ^ 1 = 1     0 ^ 0 = 0

4） 左移 m<<n 表示把m左移n位，在左移n位的時候，最左邊的n位丢棄，同時右邊補上n個0 比如

00001010 << 2 = 00101000

10001010 << 3 = 01010000

5） 右移 左移 m >> n 表示把m右移n位，在右移n位的時候，最右邊補上n個0 ，最左邊分2種情況，如果數字是一個無符号整形

則用0填補最左邊的n位，如果是一個有符号的資料，則最左邊用數字的符号填補n個資料。如果是正數，左邊補n個0，是負數左邊補n個1.

00001010 >> 2 = 00000010

10001010 >> 3 = 11110001

這裡我們可以把原資料和1進行&操作，如果二進制資料尾巴進行&操作，如果包含1的話&1操作就是1，返之結果為0，然後我們把資料進行右移一位就行。

如果一個正數要除以2，我們效率最高的是把這個資料進行右移一位。

3 代碼實作

C++版本

#include <stdio.h>
 
/*
 *二進制資料裡面包含數字1的個數
 */
int containOneNumber(int value)
{
    int count = 0;
    while (value != 0)
    {
        //這裡是(value & 1)不是（value  & 0）
        if (value & 1)
            ++count;
        //這裡是value = value >> 1,而不是value >> 1; 我們要用變量接收它
        //不然不管就隻執行了一次也就是value除以了2，是以導緻死循環。
        value = value >> 1;
    }
    return count;
    
}
 
int main(void) 
{
    int result = containOneNumber(9);
    printf("result is %d\n", result);
    return 0;
}      

java版本

public int containOneNumber(int value)
    {
        int count = 0;
        while (value != 0)
        {
            if ((value & 1) != 0)
            {
                count++;
            }
            value = value >>> 1; //>>>就是java中的無符号右移
        }
        return count;
    }      

我們知道java用 >>> 是無符号右移，右移的時候，是以最高位左邊都是0，如果這個數是負數的時候，右移的話最高位會補1，

C++版本就會變成死循環。

4 優化

方法1:

n與1做與運算，判斷n的最低位是不是為1,接着把1左移一位得到2，再和n做與運算，就能判斷n的次低位是不是1….這樣反複左移

int containOneNumber1(int n)
{
    int flag = 1;
    int count = 0;
    while (flag != 0)
    {
        if ((flag & n) != 0)
        {
            count++;
        }
        flag = flag << 1;
    }
    return count;
}      

方法2：

把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0，那麼一個整數的二進制表示中有

多少個1，就可以進行多少次這樣的操作

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

5 總結

1） 把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0，那麼一個整數的二進制表示中有多少個1

2）n與1做與運算，判斷n的最低位是不是為1,接着把1左移一位得到2，再和n做與運算，就能判斷n的次低位是不是1….這樣反複左移

3） 如果是正整數的情況下，我們可以把正整數右移動和1進行&操作，然後再去統計。