劍指offer之二進(jìn)制中1的個(gè)數(shù)

1 問題

實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)函數(shù)，輸出該二進(jìn)制數(shù)據(jù)中1的個(gè)數(shù)。例如9表示二進(jìn)制數(shù)據(jù)1001，有2位是1，因此輸入9，該函數(shù)會輸出2。

 
2 分析

我們先了解下計(jì)算機(jī)里面位運(yùn)算，有5種

1）& 這個(gè)是與操作，規(guī)律如下

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

2）| 這個(gè)是或運(yùn)算，規(guī)律如下

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

3）^ 異或運(yùn)算，規(guī)律如下

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

4） 左移 m<<n 表示把m左移n位，在左移n位的時(shí)候，最左邊的n位丟棄，同時(shí)右邊補(bǔ)上n個(gè)0 比如

    00001010 << 2 = 00101000
     
    10001010 << 3 = 01010000

5） 右移 左移 m >> n 表示把m右移n位，在右移n位的時(shí)候，最右邊補(bǔ)上n個(gè)0 ，最左邊分2種情況，如果數(shù)字是一個(gè)無符號整形

則用0填補(bǔ)最左邊的n位，如果是一個(gè)有符號的數(shù)據(jù)，則最左邊用數(shù)字的符號填補(bǔ)n個(gè)數(shù)據(jù)。如果是正數(shù)，左邊補(bǔ)n個(gè)0，是負(fù)數(shù)左邊補(bǔ)n個(gè)1.

    00001010 >> 2 = 00000010
     
    10001010 >> 3 = 11110001


這里我們可以把原數(shù)據(jù)和1進(jìn)行&操作，如果二進(jìn)制數(shù)據(jù)尾巴進(jìn)行&操作，如果包含1的話&1操作就是1，返之結(jié)果為0，然后我們把數(shù)據(jù)進(jìn)行右移一位就行。

 
如果一個(gè)正數(shù)要除以2，我們效率最高的是把這個(gè)數(shù)據(jù)進(jìn)行右移一位。

 
3 代碼實(shí)現(xiàn)

C++版本

    #include <stdio.h>
     
    /*
     *二進(jìn)制數(shù)據(jù)里面包含數(shù)字1的個(gè)數(shù)
     */
    int containOneNumber(int value)
    {
        int count = 0;
        while (value != 0)
        {
            //這里是(value & 1)不是（value  & 0）
            if (value & 1)
                ++count;
            //這里是value = value >> 1,而不是value >> 1; 我們要用變量接收它
            //不然不管就只執(zhí)行了一次也就是value除以了2，所以導(dǎo)致死循環(huán)。
            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用 >>> 是無符號右移，右移的時(shí)候，所以最高位左邊都是0，如果這個(gè)數(shù)是負(fù)數(shù)的時(shí)候，右移的話最高位會補(bǔ)1，

C++版本就會變成死循環(huán)。

 
4 優(yōu)化
方法1:

n與1做與運(yùn)算，判斷n的最低位是不是為1,接著把1左移一位得到2，再和n做與運(yùn)算，就能判斷n的次低位是不是1….這樣反復(fù)左移

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

 
方法2：

把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會把該整數(shù)最右邊一個(gè)1變成0，那么一個(gè)整數(shù)的二進(jìn)制表示中有
多少個(gè)1，就可以進(jìn)行多少次這樣的操作

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

 
5 總結(jié)

1） 把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會把該整數(shù)最右邊一個(gè)1變成0，那么一個(gè)整數(shù)的二進(jìn)制表示中有多少個(gè)1

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

3） 如果是正整數(shù)的情況下，我們可以把正整數(shù)右移動和1進(jìn)行&操作，然后再去統(tǒng)計(jì)。



作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)