《程式設計之美》讀書筆記——“求二進制數中1的個數”

“求二進制數中1的個數”

by ZelluX 

​​

​​

由電子工業出版社博文視點和w3china.org社群聯合舉辦了“看樣章, 寫書評, 赢取《​​程式設計之美——微軟技術面試心得​​​》的​​活動​​​”，詳情請見：​​http://bbs.w3china.org/dispbbs.asp?boardID=42&ID=61162​​

大家踴躍參加，活動非常熱烈。下面文章來自讀者ZelluX：

 求二進制中1的個數。對于一個位元組（8bit）的變量，求其二進制表示中"1"的個數，要求算法的執行效率盡可能的高。

先來看看樣章上給出的幾個算法：

解法一，每次除二，看是否為奇數，是的話就累計加一，最後這個結果就是二進制表示中1的個數。

解法二，同樣用到一個循環，隻是裡面的操作用位移操作簡化了。

   1:  int Count(int v)   

   2:  {   

   3:      int num = 0;

   4:      while (v) {   

   5:          num += v & 0x01;   

   6:          v >>= 1;   

   7:      }   

   8:      return num;   

   9:  } 

解法三，用到一個巧妙的與操作，v & (v -1 )每次能消去二進制表示中最後一位1，利用這個技巧可以減少一定的循環次數。

解法四，查表法，因為隻有資料8bit，直接建一張表，包含各個數中1的個數，然後查表就行。複雜度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };   

   2:      

   3:  int Count(int v) {   

   4:      return countTable[v];   

   5:  }

好了，這就是樣章上給出的四種方案，下面談談我的看法。

首先是對算法的衡量上，複雜度真的是唯一的标準嗎？尤其對于這種資料規模給定，而且很小的情況下，複雜度其實是個比較次要的因素。

查表法的複雜度為O(1)，我用解法一，循環八次固定，複雜度也是O(1)。至于資料規模變大，變成32位整型，那查表法自然也不合适了。

其次，我覺得既然是這樣一個很小的操作，衡量的尺度也必然要小，CPU時鐘周期可以作為一個參考。

解法一裡有若幹次整數加法，若幹次整數除法（一般的編譯器都能把它優化成位移），還有幾個循環分支判斷，幾個奇偶性判斷（這個比較耗時間，根據CSAPP上的資料，一般一個branch penalty得耗掉14個左右的cycle），加起來大概幾十個cycle吧。

再看解法四，查表法看似一次位址計算就能解決，但實際上這裡用到一個訪存操作，而且第一次訪存的時候很有可能那個數組不在cache裡，這樣一個cache miss導緻的後果可能就是耗去幾十甚至上百個cycle（因為要通路記憶體）。是以對于這種“小操作”，這個算法的性能其實是很差的。

這裡我再推薦幾個解決這個問題的算法，以32位無符号整型為例。

   1:  int Count(unsigned x) {   

   2:     x = x - ((x >> 1) & 0x55555555);    

   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);    

   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;    

   5:     x = x + (x >> 8);    

   6:     x = x + (x >> 16);    

   7:     return x & 0x0000003F;    

   8:  } 

這裡用的是二分法，兩兩一組相加，之後四個四個一組相加，接着八個八個，最後就得到各位之和了。

還有一個更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {

   2:     unsigned n;    

   3:      

   4:     n = (x >> 1) & 033333333333;    

   5:     x = x - n;   

   6:     n = (n >> 1) & 033333333333;   

   7:     x = x - n;    

   8:     x = (x + (x >> 3)) & 030707070707;   

   9:     x = modu(x, 63);  

   10:     return x;   

   11:  } 

首先是将二進制各位三個一組，求出每組中1的個數，然後相鄰兩組歸并，得到六個一組的1的個數，最後很巧妙的用除63取餘得到了結果。

因為2^6 = 64，也就是說 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，這裡的等号表示同餘。

這個程式隻需要十條左右指令，而且不訪存，速度很快。

由此可見，衡量一個算法實際效果不單要看複雜度，還要結合其他情況具體分析。

關于後面的兩道擴充問題，問題一是問32位整型如何處理，這個上面已經講了。

問題二是給定兩個整數A和B，問A和B有多少位是不同的。

這個問題其實就是數1問題多了一個步驟，隻要先算出A和B的異或結果，然後求這個值中1的個數就行了。

總體看來這本書還是很不錯的，比較喜歡裡面針對一個問題提出不同算法并不斷改進的風格。這裡提出一點個人的了解，望大家指正 ;-)

發現oj上有幾道類似的題，做一個總結：

整數中的1（二）​​連結：http://acm.nyist.net/JudgeOnline/problem.php?pid=281&rec=sim​​

時間限制：1000 ms  |  記憶體限制：65535

難度：5

描述

給出兩個非負32位整型範圍内的數a,b，請輸出閉區間[a,b]内所有數二進制中各個位的1的總個數。

輸入

有多組測試資料

每組測試資料隻有一行，是兩個整型數a,b(0<=a<=b<=150000000)，空格分隔。

當a,b都是0時表示輸入結束，該組輸入不用計算。

測試資料的組數不超過1000組

輸出

對于每組輸入，輸出區間[a,b]内所有數二進制中各個位的1的總個數。

樣例輸入

1 2
100 200
0 0      

樣例輸出

2
419      

求一個數化成二進制表示1的個數方法：

int found1(int a)
{
  int num = 0;
  while(a)
  {
    if(1 == a % 2)//如果是奇數，二進制的末尾一定是1
    {
      num++;
    }
    a /= 2;
  }
  return num;
}
int found2(int a)
{
  int num = 0;
  while(a)
  {
    num += a & 0x01;//和1相與，這個可比取模之後和1相比快多了哦
    a >>= 1;//右移一位，相當于除以2
  }
  return num;
}
int found3(int a)
{
  int num = 0;
  while(a)
  {
    a &= (a-1);//這個是複雜度最低的，為log2(x);x為a中1的個數。怎麼解釋呢……有點難度啊。自己模拟一下就明白了。
    num++;
  }
  return num;
}      

​​參考代碼：​​

#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{0,-1},{-1,0},{0,1},{1,0}};
int fun(int n)
{
    int m=n,t=2,ans=0;
    while(m)
    {
        ans+=(n/t)*t/2;
        if(n%t>=t/2)
        {
            ans+=n%t-t/2+1;
        }
        t=t*2;
        m=m/2;
    }
    return ans;
}
int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n,m;
    while(~scanf("%d %d",&n,&m),n+m)
    {
        if(n>m)
            swap(n,m);
        //printf("%d %d\n",fun(n),fun(m));
        printf("%d\n",fun(m)-fun(n-1));
    }
    return 0;
}      

​​标程：​​

難得想到，呵呵~我是沒有想到，先貼出代碼：暫時不懂，隻先貼下代碼，類似歸并的做法。對于相鄰的兩位，先計算這兩位的1的個數(最大是2)，比如對于32位的數來說，分成 16組，每組計算的是相鄰兩位的1的個數和，并且将這個和用新得到的數的兩位表示(2位可以最大表示4，是以可以存得下這個和，和此時最大為2)；然後對相鄰四位進行操作，計算每兩位兩位的和（這樣操作後其實是計算了原來32位數的相鄰四位的1的個數）；這樣依次類推，對于32位的數來說，隻要操作到将其相鄰16位的1的個數相加就可以得到其包含的1的個數了。​

​

#include<cstdio>
unsigned f[]={0,1,4,12,32,80,192,448,1024,2304,5120,11264,24576,53248,114688,245760,524288,1114112,2359296,4980736,10485760,22020096,46137344,96468992,201326592,419430400,872415232,1811939328};
int getpos(int n)
{
    int cnt=0;
    while(n)
    {
        cnt++;
        n>>=1;
    }
    return cnt;
}
int count1(int num)
{
    int i=0;
    while(num)
    {
     num&=(num-1);
     i++;
    }
    return i;
}
int getsub(int s)
{
    s|=s>>1;
    s|=s>>2;
    s|=s>>4;
    s|=s>>8;
    s|=s>>16;
    return s=~s;
}
int g(int m)
{
    if(!(m&(m-1))) 
    {
        int n=getpos(m);
        return f[n-1];
    }
    return g((m&(-m)))+g((m&(m-1)))+count1((getsub(m&(-m))&(m&(m-1))))*(m&(-m));
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b) && (a||b))
    printf("%d\n",g(b+1)-g(a));
}