問題描述
任意給定一個32位無符號整數n，求n的二進制表示中1的個數，比如n = 5（0101）時，回傳2，n = 15（1111）時，回傳4
這也是一道比較經典的題目了，相信不少人面試的時候可能遇到過這道題吧，下面介紹了幾種方法來實作這道題，相信很多人可能見過下面的演算法，但我相信很少有人見到本文中所有的演算法，如果您上頭上有更好的演算法，或者本文沒有提到的演算法，請不要吝惜您的代碼，分享的時候，也是學習和交流的時候，
普通法
我總是習慣叫普通法，因為我實在找不到一個合適的名字來描述它，其實就是最簡單的方法，有點程式基礎的人都能想得到，那就是移位+計數，很簡單，不多說了，直接上代碼，這種方法的運算次數與輸入n最高位1的位置有關，最多回圈32次，
int BitCount(unsigned int n)
{
unsigned int c =0 ; // 計數器
while (n >0)
{
if((n &1) ==1) // 當前位是1
++c ; // 計數器加1
n >>=1 ; // 移位
}
return c ;
}
一個更精簡的版本如下
int BitCount1(unsigned int n)
{
unsigned int c =0 ; // 計數器
for (c =0; n; n >>=1) // 回圈移位
c += n &1 ; // 如果當前位是1，則計數器加1
return c ;
}
問：如果輸入引數是int，這種方法還能奏效嗎？
如何修改？看看下面的方法：
int BitCount(int n)
{
int num = 0;
unsigned int flag = 1;
while(0 != flag)
{
if(n & flag)
num++;
flag = flag << 1;
}
return num;
}
C/C++的學習裙【七一二 二八四 七零五 】，無論你是小白還是進階者，是想轉行還是想入行都可以來了解一起進步一起學習！裙內有開發工具，很多干貨和技術資料分享！
快速法
這種方法速度比較快，其運算次數與輸入n的大小無關，只與n中1的個數有關，如果n的二進制表示中有k個1，那么這個方法只需要回圈k次即可，其原理是不斷清除n的二進制表示中最右邊的1，同時累加計數器，直至n為0，代碼如下
int BitCount2(unsigned int n)
{
unsigned int c =0 ;
for (c =0; n; ++c)
{
n &= (n -1) ; // 清除最低位的1
}
return c ;
}
為什么n &= (n – 1)能清除最右邊的1呢？因為從二進制的角度講，n相當于在n - 1的最低位加上1，舉個例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右邊的1（其實就是最高位的1，因為8的二進制中只有一個1），再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二進制表示中最右邊的1（也就是最低位的1），
查表法
動態建表
由于表示在程式運行時動態創建的，所以速度上肯定會慢一些，把這個版本放在這里，有兩個原因
-
介紹填表的方法，因為這個方法的確很巧妙，
-
型別轉換，這里不能使用傳統的強制轉換，而是先取地址再轉換成對應的指標型別，也是常用的型別轉換方法，
int BitCount3(unsigned int n)
{
// 建表
unsigned char BitsSetTable256[256] = {0} ;
// 初始化表
for (int i =0; i <256; i++)
{
BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2];
}
unsigned int c =0 ;
// 查表
unsigned char* p = (unsigned char*) &n ;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
return c ;
}
先說一下填表的原理，根據奇偶性來分析，對于任意一個正整數n
1.如果它是偶數，那么n的二進制中1的個數與n/2中1的個數是相同的，比如4和2的二進制中都有一個1，6和3的二進制中都有兩個1，為啥？因為n是由n/2左移一位而來，而移位并不會增加1的個數，
2.如果n是奇數，那么n的二進制中1的個數是n/2中1的個數+1，比如7的二進制中有三個1，7/2 = 3的二進制中有兩個1，為啥？因為當n是奇數時，n相當于n/2左移一位再加1，
再說一下查表的原理
對于任意一個32位無符號整數，將其分割為4部分，每部分8bit，對于這四個部分分別求出1的個數，再累加起來即可，而8bit對應2^8 = 256種01組合方式，這也是為什么表的大小為256的原因，
注意型別轉換的時候，先取到n的地址，然后轉換為unsigned char*，這樣一個unsigned int（4 bytes）對應四個unsigned char（1 bytes），分別取出來計算即可，舉個例子吧，以87654321（十六進制）為例，先寫成二進制形式-8bit一組，共四組，以不同顏色區分，這四組中1的個數分別為4，4，3，2，所以一共是13個1，如下面所示，
10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13
靜態表-4bit
原理和8-bit表相同，詳見8-bit表的解釋
int BitCount4(unsigned int n)
{
unsigned int table[16] =
{
0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4
} ;
unsigned int count =0 ;
while (n)
{
count += table[n &0xf] ;
n >>=4 ;
}
return count ;
}
靜態表-8bit
首先構造一個包含256個元素的表table，table[i]即i中1的個數，這里的i是[0-255]之間任意一個值，然后對于任意一個32bit無符號整數n，我們將其拆分成四個8bit，然后分別求出每個8bit中1的個數，再累加求和即可，這里用移位的方法，每次右移8位，并與0xff相與，取得最低位的8bit，累加后繼續移位，如此往復，直到n為0，所以對于任意一個32位整數，需要查表4次，以十進制數2882400018為例，其對應的二進制數為10101011110011011110111100010010，對應的四次查表程序如下：紅色表示當前8bit，綠色表示右移后高位補零，
第一次（n & 0xff） 10101011110011011110111100010010
第二次（(n >> 8) & 0xff） 00000000101010111100110111101111
第三次（(n >> 16) & 0xff）00000000000000001010101111001101
第四次（(n >> 24) & 0xff）00000000000000000000000010101011
int BitCount7(unsigned int n)
{
unsigned int table[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};
return table[n &0xff] +
table[(n >>8) &0xff] +
table[(n >>16) &0xff] +
table[(n >>24) &0xff] ;
}
當然也可以搞一個16bit的表，或者更極端一點32bit的表，速度將會更快，
平行演算法
網上都這么叫，我也這么叫吧，不過話說回來，的確有平行的意味在里面，先看代碼，稍后解釋
int BitCount4(unsigned int n)
{
n = (n &0x55555555) + ((n >>1) &0x55555555) ;
n = (n &0x33333333) + ((n >>2) &0x33333333) ;
n = (n &0x0f0f0f0f) + ((n >>4) &0x0f0f0f0f) ;
n = (n &0x00ff00ff) + ((n >>8) &0x00ff00ff) ;
n = (n &0x0000ffff) + ((n >>16) &0x0000ffff) ;
return n ;
}
速度不一定最快，但是想法絕對巧妙，說一下其中奧妙，其實很簡單，先將n寫成二進制形式，然后相鄰位相加，重復這個程序，直到只剩下一位，
以217（11011001）為例，有圖有真相，下面的圖足以說明一切了，217的二進制表示中有5個1
完美法
int BitCount5(unsigned int n)
{
unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111);
return ((tmp + (tmp >>3)) &030707070707) %63;
}
最喜歡這個，代碼太簡潔啦，只是有個取模運算，可能速度上慢一些，區區兩行代碼，就能計算出1的個數，到底有何奧妙呢？為了解釋的清楚一點，我盡量多說幾句，
第一行代碼的作用
先說明一點，以0開頭的是8進制數，以0x開頭的是十六進制數，上面代碼中使用了三個8進制數，
將n的二進制表示寫出來，然后每3bit分成一組，求出每一組中1的個數，再表示成二進制的形式，比如n = 50，其二進制表示為110010，分組后是110和010，這兩組中1的個數本別是2和3，2對應010，3對應011，所以第一行代碼結束后，tmp = 010011，具體是怎么實作的呢？由于每組3bit，所以這3bit對應的十進制數都能表示為2^2 * a + 2^1 * b + c的形式，也就是4a + 2b + c的形式，這里a,b,c的值為0或1，如果為0表示對應的二進制位上是0，如果為1表示對應的二進制位上是1，所以a + b + c的值也就是4a + 2b + c的二進制數中1的個數了，舉個例子，十進制數6（0110）= 4 * 1 + 2 * 1 + 0，這里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二進制表示中有兩個1，現在的問題是，如何得到a + b + c呢？注意位運算中，右移一位相當于除2，就利用這個性質！
4a + 2b + c 右移一位等于2a + b
4a + 2b + c 右移量位等于a
然后做減法
4a + 2b + c –(2a + b) – a = a + b + c，這就是第一行代碼所作的事，明白了吧，
第二行代碼的作用
在第一行的基礎上，將tmp中相鄰的兩組中1的個數累加，由于累加到程序中有些組被重復加了一次，所以要舍棄這些多加的部分，這就是&030707070707的作用，又由于最終結果可能大于63，所以要取模，
需要注意的是，經過第一行代碼后，從右側起，每相鄰的3bit只有四種可能，即000, 001, 010, 011，為啥呢？因為每3bit中1的個數最多為3，所以下面的加法中不存在進位的問題，因為3 + 3 = 6，不足8，不會產生進位，
tmp + (tmp >> 3)-這句就是是相鄰組相加，注意會產生重復相加的部分，比如tmp = 659 = 001 010 010 011時，tmp >> 3 = 000 001 010 010，相加得
001 010 010 011
000 001 010 010
001 011 100 101
011 + 101 = 3 + 5 = 8，（感謝網友Di哈指正，）注意，659只是個中間變數，這個結果不代表659這個數的二進制形式中有8個1，
注意我們想要的只是第二組和最后一組（綠色部分），而第一組和第三組（紅色部分）屬于重復相加的部分，要消除掉，這就是&030707070707所完成的任務（每隔三位洗掉三位），最后為什么還要%63呢？因為上面相當于每次計算相連的6bit中1的個數，最多是111111 = 77（八進制）= 63（十進制），所以最后要對63取模，
位標志法
感謝網友 @gussing提供
struct _byte
{
unsigned a:1;
unsigned b:1;
unsigned c:1;
unsigned d:1;
unsigned e:1;
unsigned f:1;
unsigned g:1;
unsigned h:1;
};
long get_bit_count( unsigned char b )
{
struct _byte *by = (struct _byte*)&b;
return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h);
}來源：https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/200480.html
標籤：C