閱讀309 返回首頁    go 阿裏雲 go 技術社區[雲棲]

編程之美之二進製數中1的個數

問題：

對於一個字節（8bit）的變量，求其二進製中1的個數，要求算法的執行效率盡可能的高。

例如把9表示成二進製是1001，有2位是1，因此如果輸入9，1的個數為2。


解法一：

可以舉一個8位二進製的例子。對於二進製操縱，我們除以一個2，原來數字就會減少一個0（向右移一位）。如果除的過程中有餘，那麼久表示當前位置有一個1。

以10100010為例：

第一次除以2時，商為1010001，餘為0

第二次除以2時，商為101000，餘為1

因此，考慮利用整形數據除法的特點，通過相除和判斷餘數的值進行分析。

  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.          if(a % 2 == 1)  
  7.          {  
  8.               count++;    
  9.          }  
  10.          a = a / 2;  
  11.     }  
  12.     return count;  
  13. }  

解法二：位操作

使用位操作同樣達到相除的目的。

使用與操作（&）來判斷最後一位是不是1，判斷完後向右移一位，繼續判斷。

可以把這個八位數與00000001進行與操作，如果結果為1則表示這個八位數最後一位為1，否則為0。

  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.          count += a & 0x01;  
  7.          a >>= 1;  
  8.     }  
  9.     return count;  
  10. }  

位操作要比除法取餘操作效率要高許多。


解法三：

作者用到一個巧妙的方法，自己與自己減1相與，（例：10100010 & 10100001 = 10100000）從而到達消去最後一位1，通過統計循環次數達到計算1的個數的目的，這個方法減少了一定的循環次數。

具體解析看看原著。

  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     while(a)  
  5.     {  
  6.         a = a & (a-1);  
  7.         count++;  
  8.     }  
  9.     return count;  
  10. }  


解法四：分支操作

解法三的複雜度降到O(M). 其中M為1的個數。這效率已經足夠高了。

如果還不滿足，還有一種方法。既然才是一個8位的數據（0~255），可以直接0~255的情況羅列出來，使用分支操作，得到答案。

這個方法看似很直接，但是效率可能會比其他方法要低。具體情況具體分析。如果a = 0比較一次就會得到答案，但是a = 255比較255次才得到答案

  1. int Count(int a)  
  2. {  
  3.     int count = 0;  
  4.     switch(a)  
  5.     {  
  6.         case 0x0:  
  7.              count = 0;  
  8.              break;  
  9.         case 0x1:  
  10.         case 0x2:  
  11.         case 0x4:  
  12.         case 0x8:  
  13.         case 0x10:  
  14.         case 0x20:  
  15.         case 0x40:  
  16.         case 0x80:  
  17.              count = 1;  
  18.              break;  
  19.         case 0x3:  
  20.         case 0x6:  
  21.         case 0xc:  
  22.         case 0x18:  
  23.         case 0x30:  
  24.         case 0x60:  
  25.         case 0xc0:  
  26.              count = 2;  
  27.              break;   
  28.         //.....  
  29.     }  
  30.     return count;  
  31. }  


解法五：查表法

直接把0~255相應1的個數直接存在數組中，采取以空間換取時間。

  1. int CountTable[256] =       
  2. {          
  3.          0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  
  4.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  5.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  6.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  7.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  8.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  9.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  10.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  11.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  12.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  13.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  14.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  15.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  16.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  17.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  18.          4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8          
  19. };  
  20.   
  21. int Count(int a)  
  22. {  
  23.     return CountTable[a];  
  24. }  

最後更新：2017-04-03 12:54:47

  上一篇：go 又是一年小年時---官三民四道土和尚五
  下一篇：go linux驅動開發--字符設備：內核等待隊列