C++如何計算二進制數中1的個數
計算二進制數中1的個數
見到計算二進制數中的1的個數的比較精巧的做法，做個筆記(其實是之前被問到瞭，所以就查瞭下…
int CountOnes(int n) {
int count = 0;
while(n) {
++count;
n = n & (n - 1);
}
return count;
}
剛看見時不太明白思路，然後自己拿筆隨便劃拉瞭下，算是搞明白瞭思路，簡單總結一下。這個方法的主要思想就是找到當前數字中最靠右的1。
思路簡單總結
n – 1(n不為0時)會使得n的最右側第一個1以及該位的右側的所有位取反，此時進行與操作，就會將該位置為0。
其實看上面那句話就行瞭，思路很簡單，完全理解不瞭思路才需要看下面的:
大致上可以分成兩種情況，當然事實上可以看成是同一種情況
- 第一種：n的最右邊是1。如果n最右邊是1的話，n-1就隻有最右邊那一位變為0，此時n & (n – 1)就相當於是把n中右邊第一位的1拿掉，比如n為0111時，n – 1就是0110，兩者相與，結果就是n – 1，此時n – 1中1的個數比n中少1，且最右側的位為0，已經轉變為第二種情況。
- 第二種：n的最右邊是0。此時計算n – 1時，需要向上借位，一直借到n的最右側的第一個1。例如n為1000時，n – 1就是0111，此時可以發現，n的第一個1的右側的所有位都變成瞭1，並且原來是1的位變成瞭0。註意初始時n的第一個1的右側的所有位都是0，計算n – 1後這些位都變成瞭1，此時再做與操作，這些位都會變成0。所以效果就是"n的右側第一個為1的位被置為0"。
最後當n中不存在為1的位時，n的值等於0，while循環退出。這種做法相對於直接從右往左靠移位和與的做法來說更好一些，不需要遍歷所有的位，也少瞭不少的判斷，運行時間與n中1的個數相關。
C++ 1的個數簡單解法
問題描述
輸入正整數n，判斷從1到n之中，數字1一共要出現幾次。例如1123這個數，則出現瞭兩次1。
例如15，那麼從1到15之中，一共出現瞭8個1。
輸入格式
- 一個正整數n
輸出格式
- 一個整數，表示1出現的資料
樣例輸入
15
樣例輸出
8
數據規模和約定
- n不超過30000
#include <iostream>
using namespace std;
int main(){
int n;
int cnt = 0; //用來記錄1的個數
cin >> n;
for(int i=1;i<=n;i++){
int j = i; //j用來存放每次循環後更新過的i值
while(j){ //循環依次對j的個位十位百位。。。位進行對一取餘
if(j%10==1){
cnt++;
}
j /= 10;
}
}
cout << cnt << endl;
return 0;
}
以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。