编程之美：1的数目

比眉伴天荒 2022-06-05 04:19 201阅读 0赞

### 获取N的二进制中1的个数 ###

最简便解法，直接用n与(n-1)进行与操作，直到n=0，程序复杂度只与1的个数有关

void getBinOneNum(int n) {
        /*获取n二进制中1的个数*/
        int count = 0;
        while (n)
        {
            n &= (n - 1);
            count++;
    
        }
        cout << count;
    }

### 获取小于等于N正整数中1的数目： ###

规律为：求当前位的高位，低位和位数

> 当前位=0：个数=高位\*10^位数  
> 当前位=1：个数=高位\*10^位数+低位+1  
> 当前位>1：个数=（高位+1）10^\*位数

累加即可得到结果

void getOneNum(int N) {
        //获得小于等于N的所有1出现的个数
        unsigned long long icount = 0; //1的位数统计
        unsigned long long iFactor = 1; //10的位数次方
        unsigned long long iLowerNum = 0; //低位
        unsigned long long iHeigherNum = 0; //低位
        unsigned long long iCurrNum = 0; //当前位
        while (N / iFactor) {
            iLowerNum = N - (N / iFactor)*iFactor; 
            iHeigherNum=N / (iFactor * 10);
            iCurrNum = (N / iFactor) % 10;
            switch (iCurrNum)
            {
            case 0:
                icount += iHeigherNum*iFactor;
                break;
            case 1:
                icount += iHeigherNum*iFactor + iLowerNum + 1;
                break;
            default:
                icount += (iHeigherNum + 1)*iFactor;
                break;
            }
            iFactor *= 10;
        }
        cout << icount;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关 [算法系列之三十二]1的数目

题目 > Given an integer n, count the total number of digit 1 appearing in all non-negati

骑猪看日落/ 2023年06月25日 03:08/ 0 赞/ 22 阅读

相关 Java并发编程之美

一，二待更新... 三. volatile关键字能够保证线程可见性，当一个线程修改共享变量时，能够保证对另外一个线程可见性，但是注意他不能够保证共享变量的原

川长思鸟来/ 2022年11月05日 12:49/ 0 赞/ 205 阅读

相关编程之美笔记

1. 点是否在三角形内解法1：如果点在三角形内部，该点和另外的三个点所组成的三个三角形的面积之和和原三角形的面积相等。 ![Center][]

我就是我/ 2022年09月17日 07:28/ 0 赞/ 220 阅读

相关编程之美总结

2.1.求二进制中1的个数除数取余 v & (v - 1) 2.2.不要被阶乘吓倒：求N!中末尾有多少个0 N! = 2^a\3^b\5^c\7^d\11^e

缺乏、安全感/ 2022年08月11日 12:59/ 0 赞/ 251 阅读

相关编程之美-求二进制1的个数

一个在常见的题目，但是看到编程之美的时候才发现，方法真多，今天来总结一下：解法一可以举出一个八位的二进制例子来进行分析。对于一个二进制操作，我们知道，除以一个2，原来的

水深无声/ 2022年08月06日 14:08/ 0 赞/ 161 阅读

相关求二进制数中1的个数（编程之美）

求二进制数中1的个数题目描述：对于一个字节1BYTE = 8 bits的无符号变量，求其二进制表示中1的个数，要求算法的执行效率尽可能高。题目分析：可以吧

刺骨的言语ヽ痛彻心扉/ 2022年08月06日 12:09/ 0 赞/ 188 阅读

相关 LeetCode-Number of Digit One（编程之美-1的数目）

Given an integer n, count the total number of digit 1 appearing in all non-negative inte

ゝ一纸荒年。/ 2022年08月04日 13:39/ 0 赞/ 188 阅读

相关编程之美：1的数目

获取N的二进制中1的个数最简便解法，直接用n与(n-1)进行与操作，直到n=0，程序复杂度只与1的个数有关 void getBinOneNum(int n)

比眉伴天荒/ 2022年06月05日 04:19/ 0 赞/ 202 阅读

相关 Java 编程之美：并发编程

借用 Java 并发编程实践中的话，编写正确的程序并不容易，而编写正常的并发程序就更难了！相比于顺序执行的情况，多线程的线程安全问题是微妙而且出乎意料的，因为在没有进行适当

迈不过友情╰/ 2022年05月21日 03:54/ 0 赞/ 299 阅读

相关 Java并发编程之美(1) ReentrantLock重入锁

Java并发编程之美(1）ReentrantLock重入锁简介 lock tryLock 公平锁简介

素颜马尾好姑娘i/ 2022年03月26日 03:39/ 0 赞/ 292 阅读