劍指Offer：面試題15——二進制中1的個數（java）

文章目錄

• 二進制中1的個數
• • 1. 題目描述
  • 2. 前提知識補充
  • • 2. 1 位運算規律
    • 2.2 左移右移運算
    • 2.3 位運算的實質
  • 3. 算法思路一
  • • 3.1 除法
    • 3.2 位運算
    • 3.3 算法漏洞
  • 4.算法思路二
  • 5. 算法思路三（最優解法）

二進制中1的個數

1. 題目描述

• 輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

2. 前提知識補充

2. 1 位運算規律

2.2 左移右移運算

• 左移運算 m << n 就是将原資料 m 的左邊去掉n位，在右邊補上n個零即可
  • 0110010 << 2 = 1001000
  • 10001010 << 3 = 01010000
• 右移運算 m >> n 就是将原資料m右邊丢去n位，但是在補位的時候情況就比較複雜一點，因為涉及到有符号數和無符号數！
  • 無符号數：右邊丢n位，左邊補n個0
    • 00001010 >> 2 = 00000010
  • 有符号數：如果是正數就用0補位，如果是負數就用1補位
    • 00001010 >> 2 = 00000010
    • 10001010 >> 2 = 11100010

2.3 位運算的實質

• 這裡我們以16位例：10000
• 16右移1位時： 16 >> 1 = 01000 = 8 ，即右移一位相當于除以了2
• 16右移2位時： 16 >> 2= 00100 = 4 ，即右移一位相當于除以了2的平方
• 16左移1位時： 16 << 1 = 100000 = 32 ，即左移一位相當于乘以了2

3. 算法思路一

3.1 除法

• 針對于十進制數，我們想要的肯定是轉二進制，這樣才可以清晰的判斷有多少個1，但是實際上我們如果全部轉為二進制再最後來看的話顯然就顯得複雜了，是以應該在我們轉二進制的過程中就可以進行判斷。
• 這裡我們先使用除法的方式将十進制數轉二進制，以30為例：
  • 30 % 2 = 0 ， 0為二進制的最後一位， 再将 30 / 2 = 15
  • 15 % 2 = 1 ， 1為二進制的倒數第二位 ，再将15 / 2 = 7
  • 7 % 2 = 1，
  • 3 % 2 = 1，
  • 1 % 2 = 1
  • 最終30的二進制為 11110 （也就是從下往上寫即可）
• 至此我們就明白了，隻要每次判斷模2的餘數是1還是0即可
• 該算法的思路就是每次求出二進制的末尾位，然後進行判斷
• 但是此算法是有漏洞的！後面會講到

/**
     * 除法
     * @param x
     * @return
     */
    public static int countOne(int x){
        int count = 0;
        while(x != 0){
            if(x % 2 == 1){
                count++;
            }
            x = x / 2;
        }
        return  count;
    }
           

3.2 位運算

• 其實在很多架構底層的運算中，一般不使用除法，因為位運算的效率明顯高于除法！是以對于上面的寫法，我們可以進行改進，那就是使用位運算。
• 上面也提到了，除以2其實就是右移一位！
• 其次，在判斷末尾位是否為1的時候，可以直接将數字與 1 做位與運算

/**
     * 位運算  輸入為負數是會有死循環
     * @param x
     * @return
     */
    public static int countOne1(int x){
        int count = 0;
        while(x != 0){
            if((x & 1) == 1){
                count++;
            }
            x = x >> 1;
        }

        return count;
    }
           

3.3 算法漏洞

• 這裡就直接放書上的原話，指的就是輸入如果是負數的時候就會陷入死循環

  ，因為x永遠不可能為0

  

4.算法思路二

• 剛剛我們每次将 x 與 1 做與運算來判斷最後一位二進制尾數是否為1，然後不斷的對x做右移運算，正式因為對x做了右移運算是以才會導緻負數的情況。那我們就避免對x做右移運算，轉而對 1 做運算
• 我們将 x 與 1做與運算判斷尾數是否為1，之後将 1做左移運算變成2 ，再将 x 與 2做與運算，這樣可以判斷 次末尾數是否為1，再将 1 變成 4，判斷倒數第三位的情況。
• 也就是不斷的将1 變成2 ，4 ，8 去判斷倒數第一位，倒數第二位的情況
• 這個循環次數等于二進制數的位數，實際上後面還有最優的解法

/**
     * 位運算  
     * 改進 但是循環32位
     * @param x
     * @return
     */
    public static int countOne2(int x){
        int count = 0;
        int flag = 1;
        while(flag != 0){
            if((x & flag) != 0){  //不等于0  因為 9&8 結果為8
                count++;
            }
            flag = flag << 1;
        }

        return count;
    }
           

5. 算法思路三（最優解法）

• 這種思路其實就是為了不循環那麼多次，而是有多少個1循環多少次

  

/**
     * 最優解法
     * @param x
     * @return
     */
    public static int countOne3(int x){
        int count = 0;
        while(x != 0){
            count++;
            x = x & x - 1;
        }

        return count;
    }