二進制中1的個數

zsirfs 發布于2019-08-16 12:36 / 3221人閱讀

摘要：題目輸入一個數不管是幾進制，輸出這個數二進制表示中的個數。代碼如下相當于這個解法中循環次數等于目標整數二進制的位數，位整數就需要循環次，方案三給出目標整數中有幾個就只循環幾次的方案。舉個例子一個二進制數，從右邊數起第三位是處于最右邊的一個。

題目：輸入一個數（不管是幾進制），輸出這個數二進制表示中1的個數。比如輸入 9 應該輸出 2 ；輸入0x1F（31）應該輸出 5 。（16進制表示是在前面加 0x ）

方案一：

我最開始的想法是把這個數轉化成二進制，因為之前做過十進制轉二進制所以理所應當的這么想了，最后感覺不太對，要這么寫那的寫幾個進制轉換類啊，而且效率不高。

方案二：

然后看了一下書，書上的做法很巧妙：先查看目標數字末尾位是0還是1，這可以通過與一個1做與運算得到結果，然后把目標數字右移一位，繼續與1做與，聲明一個計數器count，持續加就好。
不過也給出了缺陷，缺陷在于如果目標數字是負數（負數的符號位也要算進總的1的個數里）不光沒法的到正確結果，還會讓陷入死循環：把負數0x8000右移一位，其實是變成了0xc000，多移幾次就變成0xffff然后
死循環了，因為左移和右移是基于這樣的原則：
                左移時最左邊的n位被丟棄，同時在最右邊補上n個0。
                右移時如果是正數補0，負數在最左邊補1.

所以更新方案：把1左移，循環一次就左移一次，這樣目標數每一位的1就都不會放過，與運算每得到一個1就count++。反正最后1移到最后就溢出了變成0000000000，這就是循環中止條件。
代碼如下：

public class Jianzhi{
    public static void main(String[] args){
        int num = 0xFF ;  //相當于int num = 31 ;
        int flag = 1 ;
        int count = 0 ;
        while( flag != 0 ){
            if( (num&flag) != 0 ){
                count++ ;
            }
            flag = flag << 1 ;
        }
        System.out.print(count);
    }
}

這個解法中循環次數等于目標整數二進制的位數，32位整數就需要循環32次，方案三給出目標整數中有幾個1就只循環幾次的方案。

方案三：
如果一個整數不為0，那么這個整數至少有一位是1。如果我們把這個整數減1，那么原來處在整數最右邊的1就會變為0，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響。
舉個例子：一個二進制數1100，從右邊數起第三位是處于最右邊的一個1。減去1后，第三位變成0，它后面的兩位0變成了1，而前面的1保持不變，因此得到的結果是1011.我們發現減1的結果是把最右邊的一個1開始的所有位都取反了。這個時候如果我們再把原來的整數和減去1之后的結果做與運算，從原來整數最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000.也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0.那么一個整數的二進制有多少個1，就可以進行多少次這樣的操作。

基于這種思想有如下代碼：

public class Jianzhi{
    public static void main(String[] args){
        int num = 0xFF ;  //相當于int num = 31 ;
        int flag = num-1 ;
        int count = 0 ;
        while(num != 0 ){
            num = num & flag ;
            flag = num - 1 ;
            count ++ ;
        }
        System.out.print(count);
    }
}

云服務器 GPU云服務器 php中二進制的代碼 java中寫入幾個數 python中二進制 java中轉化二進制

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71395.html

【劍指offer】一個數的二進制序列中1的個數

摘要：圖解第二種算法圖解代碼示例算法如果為真，說明拿到的是二進制序列的個數為算法為的時候說明已經拿完了，循環終止二進制序列中的個數以上代碼，還可做優化在此僅作參考，若有更好的算法，還望能夠私信告知，多謝各位。 ?前言?：算法是一個程序員的內功，能很好的體現程序員的編程思維，通過學習和掌握常見的算...

weknow619 2021-09-02 15:15 評論0 收藏0
劍指offer：二進制中1的個數（Java）

摘要：問題描述輸入一個整數，輸出該數二進制表示中的個數。其中負數用補碼表示。思路方法將二進制變成字符數組，遍歷數組統計的個數，這種辦法不需要考慮正負數。遍歷字符數組，統計的個數判斷該位是否是，如果是就，否則執行下一次循環。的二進制表示想右移一位。 1.問題描述輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。 2.思路方法1：將二進制變成字符數組，遍歷數組統計1的個數，這...

lifesimple 2019-08-16 18:36 評論0 收藏0
別人家的面試題：統計“1”的個數

摘要：長話短說，讓我們來看一道題統計的個數給定一個非負整數，對于任意，，計算的值對應的二進制數中的個數，將這些結果返回為一個數組。第二版本的時間復雜度是最后版本的時間復雜度是，是的二進制數中的的個數，介于之間。小胡子哥@Barret李靖給我推薦了一個寫算法刷題的地方leetcode.com，沒有ACM那么難，但題目很有趣。而且據說這些題目都來源于一些公司的面試題。好吧，解解別人公司的面試題...

SQC 2019-08-19 18:27 評論0 收藏0