亲宝软件园·资讯

展开

计算二进制数中1的个数

no_367 人气:0

计算二进制数中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的值等于0,while循环退出。这种做法相对于直接从右往左靠移位和与的做法来说更好一些,不需要遍历所有的位,也少了不少的判断,运行时间与n中1的个数相关。

C++ 1的个数简单解法

问题描述

输入正整数n,判断从1到n之中,数字1一共要出现几次。例如1123这个数,则出现了两次1。

例如15,那么从1到15之中,一共出现了8个1。

输入格式

输出格式

样例输入

15

样例输出

8

数据规模和约定

#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;
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。

加载全部内容

相关教程
猜你喜欢
用户评论