编程之美读书笔记2.1—求二进制数中1的个数
解法一：
可以舉一個8位二進制的例子。對于二進制操縱，我們除以一個2，原來數字就會減少一個0（向右移一位）。如果除的過程中有余，那么久表示當前位置有一個1。
以10100010為例：
第一次除以2時，商為1010001，余為0
第二次除以2時，商為101000，余為1
因此，考慮利用整形數據除法的特點，通過相除和判斷余數的值進行分析。
?
解法二：位操作
?
使用位操作同樣達到相除的目的。
使用與操作（&）來判斷最后一位是不是1，判斷完后向右移一位，繼續判斷。
可以把這個八位數與00000001進行與操作，如果結果為1則表示這個八位數最后一位為1，否則為0
int Count(int a) {int count = 0;while(a){count += a & 0x01;a >>= 1;}return count; }解法三：
作者用到一個巧妙的方法，自己與自己減1相與，（例：10100010 & 10100001 = 10100000）從而到達消去最后一位1，通過統計循環次數達到計算1的個數的目的，這個方法減少了一定的循環次數。
具體解析看看原著。
int Count(int a) {int count = 0;while(a){a = a & (a-1);count++;}return count; }解法四：分支操作
解法三的復雜度降到O(M). 其中M為1的個數。這效率已經足夠高了。
如果還不滿足，還有一種方法。既然才是一個8位的數據（0~255），可以直接0~255的情況羅列出來，使用分支操作，得到答案。
這個方法看似很直接，但是效率可能會比其他方法要低。具體情況具體分析。如果a = 0比較一次就會得到答案，但是a = 255比較255次才得到答案
?
解法五：查表法
直接把0~255相應1的個數直接存在數組中，采取以空間換取時間。時間復雜度為1。
int CountTable[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(int a) {return CountTable[a]; }動態建表
由于表示在程序運行時動態創建的，所以速度上肯定會慢一些，把這個版本放在這里，有兩個原因
1. 介紹填表的方法，因為這個方法的確很巧妙。
2. 類型轉換，這里不能使用傳統的強制轉換，而是先取地址再轉換成對應的指針類型。也是常用的類型轉換方法。
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
?
?
靜態表-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
?
?
5.平行算法
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
?
總結
以上是生活随笔為你收集整理的编程之美读书笔记2.1—求二进制数中1的个数的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Go基础编程：格式化输出、类型转换、类型
- 下一篇： LRU原理及其实现（C++）