<<編程之美>>中有這么個題目：對于一個字節的無符號整形變量，求其二進制表達形式中“1”的個數。

　　基礎算法：輾轉相除法

　　輾轉相除法是十進制采用的算法，該算法如下：

int count_one_cnt(int value) {int cnt = 0;while (value){if (value % 2 == 1){cnt += 1;}value /= 2;}return cnt; }

　　上述算法的時間復雜度O(logV)(V是value比特數)，上述算法的操作對象的級別是“數”級別的，題目的要求是“位”級別的，因此如果能夠通過位運行完成題目要求功能，將會更加高效：1）除法采用右移實現；2）通過與1位與運算判斷是否有1的存在。

int count_one_cnt(int value) {int cnt = 0;while (value){cnt += value & 1;value >>= 1;}return cnt; }

　　位與法：

　　上面的兩個算法時間復雜度均依賴于欲求的數據類型在存儲空間中占有的比特數，位與法算法復雜度則僅與待求數據中1的個數相關。首先，觀察某個數a與a-1:在二進制下，a-1在最右端加上1就等于a，a與a-1進行位與運算則會消除最右邊的1，可以從以下角度理解;

　　1）a與a-1僅差一個1，而這個1是從a-1最低端加上便等于a

　　2）假設a最低端出現的位置pos，pos后面均是0，因此與b位與運算，pos位置后面均是0

　　3）a-1的對應pos位置，一定是0。假設a-1在pos位置等于1，a-1后面必然均是0，否則a-1將會大于a，但根據1）a等于a-1處最低端位加1，而a-1從pos位置開始均是0，在a-1最低端位加1得到的a，在pos位置到最低端一定有一個1，與2）矛盾。

　　雖然理解起來有些繞彎，但是代碼卻是非常簡潔的：

int count_one_cnt(int value) {int cnt = 0;while (value){value &= value-1;cnt += 1;}return cnt; }

　　位圖法：

　　<<編程之美>>提到了這種方法：8bit的無符號整數的范圍是[0, 255)，因此直接將256個數還有的1位數做出表的形式，以時間換空間~實現方法在此省略。

　　Hamming weight方法：

　　Hamming weight:是指在給定的字符串中，所有不等于0的字符的個數，在一串二進制的字符串中，等于該二進制中1的個數。Hamming weight方法的一種快速實現，采用了“隔位相加”的方法：相鄰位相加，并存在與當前位置中。算法過程如下(來源與維基百科)：

可以從下圖快速理解算法的執行過程：

　　

實現方法在此不一一列出，有興趣可以參考維基百科中給出了三種實現方法~

轉載于:https://www.cnblogs.com/wangbogong/p/3240951.html

總結

以上是生活随笔為你收集整理的求二进制数中1的个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。