計(jì)算二進(jìn)制數(shù)中1的個(gè)數(shù)

見到計(jì)算二進(jìn)制數(shù)中的1的個(gè)數(shù)的比較精巧的做法，做個(gè)筆記(其實(shí)是之前被問到了，所以就查了下…

int CountOnes(int n) {
?? ?int count = 0;
?? ?while(n) {
?? ??? ?++count;
?? ??? ?n = n & (n - 1);
?? ?}
?? ?return count;
}

剛看見時(shí)不太明白思路，然后自己拿筆隨便劃拉了下，算是搞明白了思路，簡(jiǎn)單總結(jié)一下。這個(gè)方法的主要思想就是找到當(dāng)前數(shù)字中最靠右的1。

思路簡(jiǎn)單總結(jié)

n - 1(n不為0時(shí))會(huì)使得n的最右側(cè)第一個(gè)1以及該位的右側(cè)的所有位取反，此時(shí)進(jìn)行與操作，就會(huì)將該位置為0。

其實(shí)看上面那句話就行了，思路很簡(jiǎn)單，完全理解不了思路才需要看下面的:

大致上可以分成兩種情況，當(dāng)然事實(shí)上可以看成是同一種情況

• 第一種：n的最右邊是1。如果n最右邊是1的話，n-1就只有最右邊那一位變?yōu)?，此時(shí)n & (n - 1)就相當(dāng)于是把n中右邊第一位的1拿掉，比如n為0111時(shí)，n - 1就是0110，兩者相與，結(jié)果就是n - 1，此時(shí)n - 1中1的個(gè)數(shù)比n中少1，且最右側(cè)的位為0，已經(jīng)轉(zhuǎn)變?yōu)榈诙N情況。
• 第二種：n的最右邊是0。此時(shí)計(jì)算n - 1時(shí)，需要向上借位，一直借到n的最右側(cè)的第一個(gè)1。例如n為1000時(shí)，n - 1就是0111，此時(shí)可以發(fā)現(xiàn)，n的第一個(gè)1的右側(cè)的所有位都變成了1，并且原來是1的位變成了0。注意初始時(shí)n的第一個(gè)1的右側(cè)的所有位都是0，計(jì)算n - 1后這些位都變成了1，此時(shí)再做與操作，這些位都會(huì)變成0。所以效果就是"n的右側(cè)第一個(gè)為1的位被置為0"。

最后當(dāng)n中不存在為1的位時(shí)，n的值等于0，while循環(huán)退出。這種做法相對(duì)于直接從右往左靠移位和與的做法來說更好一些，不需要遍歷所有的位，也少了不少的判斷，運(yùn)行時(shí)間與n中1的個(gè)數(shù)相關(guān)。

C++ 1的個(gè)數(shù)簡(jiǎn)單解法

問題描述

輸入正整數(shù)n，判斷從1到n之中，數(shù)字1一共要出現(xiàn)幾次。例如1123這個(gè)數(shù)，則出現(xiàn)了兩次1。

例如15，那么從1到15之中，一共出現(xiàn)了8個(gè)1。

輸入格式

• 一個(gè)正整數(shù)n

輸出格式

• 一個(gè)整數(shù)，表示1出現(xiàn)的資料

樣例輸入

15

樣例輸出

8

數(shù)據(jù)規(guī)模和約定

• n不超過30000

#include <iostream>
using namespace std;

int main(){
?? ?int n;
?? ?int cnt = 0; //用來記錄1的個(gè)數(shù)
?? ?cin >> n;
?? ?for(int i=1;i<=n;i++){
?? ?int j = i; //j用來存放每次循環(huán)后更新過的i值
?? ?while(j){ //循環(huán)依次對(duì)j的個(gè)位十位百位。。。位進(jìn)行對(duì)一取余
?? ??? ?if(j%10==1){?
?? ??? ??? ?cnt++;?? ?
?? ??? ?}
?? ??? ?j /= 10;
?? ? }
?? ?}
?? ?cout << cnt << endl;
?? ?return 0;
}

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。