Chapter1: 位運算的奇技淫巧
3. 題解：計算無符號二進制數(shù)中1的個數(shù)
題目
計算無符號整數(shù)的二進制表示中1的個數(shù)
算法
移位統(tǒng)計法(普通法)
這個簡單算法對于每一位都需要一次操作，直到結束。所以對于32位字長，且只有最高位為1時（即最壞情況），這個算法會操作32次。
#include<iostream>
#include<cstdlib>
using namespace std;
/**Problem: 計算無符號整數(shù)v的二進制中1的個數(shù)**/
/*移位統(tǒng)計法*/
int main(){
unsigned int v=3;
unsigned int count=0; // 保存計算的結果
for (;v!=0; v >>= 1)//將變量v進行移位，直到最高位的1被右移舍掉后(因此該算法對有符號數(shù)無效，移位其符號位為1)
{
count += (v & 1);//如果v的最低位為1，則(v&1)會返回1，否則為0(&運算是按位與)
}
printf("%d\n",count);
return 0;
}
快速法
這種方法速度比較快，其運算次數(shù)與輸入n的大小無關，只與n中1的個數(shù)有關。
如果n的二進制表示中有k個1，那么這個方法只需要循環(huán)k次即可。
其原理是不斷清除n的二進制表示中最右邊的1，同時累加計數(shù)器，直至n為0。
v&(v-1) 得到的是 v 去掉最低位的1 后的數(shù)
為什么v &= (v – 1)能清除最右邊的1呢？因為從二進制的角度講，v相當于在v - 1的最低位加上1
比如 7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二進制表示中最右邊的1（也就是最低位的1）
又比如 8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右邊的1（其實就是最高位的1，因為8的二進制中只有一個1）
int bitCount2(unsigned int v){
unsigned int count=0;
for(;v!=0;count++){
v&=(v-1);// v&(v-1)= v去掉最低位的1后的數(shù)
}
return count;
}
擴展
問題：用一條語句判斷一個正整數(shù)是不是2的正整數(shù)次方
算法：
如果一個數(shù) N 是 2 的整數(shù)次方，即 N=2^n ，則說明 N 的二進制形式為 000...1...00 的形式，即只有 1 位是 1 ，其余位是 0 。N&(N-1) 返回的是去掉最低位的1的結果，如果結果為0，說明只有1個1
if(N&(N-1)==0
查表法
其實就是建立一張表，這張表存儲了每一個 [0,255] 之間的數(shù)的二進制表示中 1 的個數(shù)，
對于32 bit 的無符號整數(shù) unsigned int , 將其切分為 4 段，每段 8 bit ,查表分別求出每段的 1 的個數(shù)再求和即可。
動態(tài)建表是在程序運行時創(chuàng)建表，所以速度會慢一些，靜態(tài)表則會快一些，都是在用空間換時間。
對于靜態(tài)表，搞一個16 bit([0,2^16]) 的表，或者更極端一點 32 bit 的表，速度將會更快。
動態(tài)建表
由于表示在程序運行時動態(tài)創(chuàng)建的，所以速度上肯定會慢一些，把這個版本放在這里，有兩個原因
介紹填表的方法，因為這個方法的確很巧妙。
類型轉換，這里不能使用傳統(tǒng)的強制轉換，而是先取地址再轉換成對應的指針類型。也是常用的類型轉換方法。
填表原理：
對于任意一個正整數(shù)v，分奇數(shù)和偶數(shù)兩種情況討論：
-
如果v是偶數(shù)，那么v的二進制中1的個數(shù)與v/2中1的個數(shù)是相同的。
比如4和2的二進制中都有一個1，6和3的二進制中都有兩個1。
為啥？因為v是由v/2左移一位而來，而移位并不會增加1的個數(shù)。
-
如果v是奇數(shù)，那么v的二進制中1的個數(shù)是v/2中1的個數(shù)+1。
比如7的二進制中有三個1，7/2 = 3的二進制中有兩個1。
為啥？因為當v是奇數(shù)時，v相當于v/2左移一位再加1。
查表原理：
對于任意一個32位 無符號整數(shù)，將其分割為 4 部分，每部分 8 bit ，對于這四個部分分別求出 1 的個數(shù)，再累加起來即可。而 8bit 對應 2^8 = 256種01組合方式，這也是為什么表的大小為256的原因。
注意類型轉換的時候，先取到 v 的地址，然后轉換為 unsigned char* ，這樣一個 unsigned int（4 bytes=32 bit） 對應四個 unsigned char（1 bytes=8 bit），分別取出來計算即可。
舉個例子，以87654321（十六進制）為例，先寫成二進制形式, 8bit一組，共4組，這4組中1的個數(shù)分別為4，4，3，2，所以一共是13個1，如下面所示。
<font color=red > 10000111</font> <font color="black">01100101</font> <font color="blue"> 01000011</font> <font color="green"> 00100001</font> = 4 + 4 + 3 + 2 = 13
/*動態(tài)查表法*/
int bitCount3(unsigned int v){
//建表
unsigned char bitsSetTable[256]={0};
//初始化表
for(int i=0;i<256;i++){
bitsSetTable[i]=bitsSetTable[i/2]+(i&1);
}
unsigned int count=0;
//查表
unsigned char *p=(unsigned char*) &v;
//p[0]為 v二進制表示的低位的后8位對應的數(shù)值，...,p[3]為高位前8位對應的值
//bitsSetTable[p[0]]即為p[0]值對應的二進制的1的個數(shù)
count = bitsSetTable[p[0]]+
bitsSetTable[p[1]]+
bitsSetTable[p[2]]+
bitsSetTable[p[3]];
return count;
}
靜態(tài)建表
首先構造一個包含256個元素的表 table ，table[i] 即數(shù)值 i 的二進制 1 的個數(shù)，這里的 i 是 [0,255] 之間任意一個值。
對于任意一個 32bit 無符號整數(shù) n ，我們將其拆分成4個 8bit ，然后分別求出每個8bit 中 1 的個數(shù)，再累加求和即可.
這里用移位的方法，每次右移8位，并與 0xff(11111111) 相與，取得最低位的 8bit (高位的與0相與所以結果為0)，查表得到對應的 1 的個數(shù)，累加后繼續(xù)移位，如此往復，直到v為0。
所以對于任意一個32位整數(shù)，需要查表4次。
以十進制數(shù) 2882400018 為例，其對應的二進制數(shù)為 10101011110011011110111100010010，對應的4次查表過程如下：紅色表示當前8bit ，綠色表示右移后高位補零。
第一次（v & 0xff） 101010111100110111101111 <font color="red">00010010</font>
第二次（(v >> 8) & 0xff） <font color="green">00000000</font> 1010101111001101 <font color="red">11101111</font>
第三次（(v >> 16) & 0xff）<font color="green">00000000 00000000 </font>10101011 <font color="red">11001101</font>
第四次（(v >> 24) & 0xff）<font color="green">00000000 00000000 00000000</font> <font color="red">10101011</font>
/*靜態(tài)建表法*/
int bitCount4(unsigned int v){
{
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,
};
int count=0;
count = table[v&0xff]+table[(v>>8)&0xff]+
table[(v>>16)&0xff]+table[(v>>24)&0xff];
}
}
