统计1的个数问题

清疚 2022-08-12 00:18 80阅读 0赞

时间：2014.09.06

地点：基地

一、问题描述

给定一个十进制正整数N，从1，2，... ，N ，求出所有出现1的个数。比如N=12时，有 1 10 11 12三个数中有1出现，出现次数为5次，返回结果为5 。

二、分析

## 1.暴力法 ##

一般暴力法都比较容易想到，虽然效率上不是很好，但往往能从暴力法中发现一些规律或技巧，所以暴力法还是值得思考的。

首先想到真对某一个数字统计1的个数问题，即是不断的将数字右移，看最低位是否为1，这个问题解决后，剩下的问题就是对数据集的每一个数字进行一次遍历，统计1的总数的简单问题了。

对于十进制数字右移有一些常用的常识，值得好好加以利用，虽然说是常识，但一不小心容易出错。

第一条：十进制数字N每右移一位，即是将该十进制数字除以10，每左移移位即是将该十进制数字乘以10。这种技巧在二进制数字表达方式也是如此，二进制数字右移即除以2，左移即乘以2，不过对于二进制而言，有效率更高的移位操作。

第二条：获取一个十进制数字的最低位即是将该十进制数字模10。在二进制数字中也一样，不过那里更为人所知的是换了一种说法，模2看奇偶性，模2结果有两种，为1则最低位为1，为奇数，模2结果为0则最低位为0，为偶数。

暴力法只涉这两条，看十进制数字最低位，因此不断地右移看最低位即可。代码如下：

static int get_ones_count(int n)
    {
    	int count = 0;
    	while (n != 0)
    	{
    		count += (n % 10 == 1) ? 1 : 0;
    		n /= 10;
    	}
    	return count;
    }
    int GetTotalOnes(int N)
    {
    	int count = 0;
    	for (int i = 1; i <= N; ++i)
    	{
    		count += get_ones_count(i);
    	}
    	return count;
    }

## 2.深入分析 ##

浅层分析只能得暴力法，粗暴而不给力，如果能利用数字之间的一些规律和信息，变能更有效的解决问题。《编程之美》里有谈论到这个问题的分析，但我更喜欢倾向于借助高中数学里的排列组合知识，虽然道理大致相同，但更容易理解，思路如下：

对于一个十进制正整数数不妨设其表示为N=123x56，百位用x表示，目的是统计集合\[ 1，2，...... 123x56 \]中1的个数，将集合中每个数字都用0补齐为6位数，对结果毫无影响，于是接下来的工作就是统计该集合中所有数的个位、十位、百位、...为1的情况。假设此时要统计百位为1的情况。即问题转换为：集合中百位为1且比123x56小的问题。

第一种情况：N的百位x=0，那么在集合中数的模式为，百位以上部分可取【000,001，...,122】均可，共123中情况，百位固定（因为正是要统计百位为1的情况），百位一下的位没一位都有10中情况，组合起来即122\*10\*10种。于是总结为：

若给定十进制整数中目标位为0，则所有数中该位上1的个数为：

目标位高位数字\*（10^目标位以下数字的位数）

第二种情况：N的百位x=1，首先上面情况包含在其中，即高位部分取【000,001,...,122】时和上面情况一一样，另外，当取123也还有部分满足，这一部分表现为低位取【00,01，...56】。于是可总结为：

若给定十进制整数中目标位为0，则所有数中该位上1的个数为：

目标位以上的高位数字\*（10^目标位以下数字的位数）+目标位以下的低位数字+1

第三种情况：N的百位为x>1，则更加容易分析，即高位部分取【000,001,002,......123】供，123中情况，低位可能依旧。于是可总结为：

若给定十进制整数中目标位大于1，则所有数中该位上1的个数为：

（目标位以上的高位数字+1）\*（10^目标位以下数字的位数）

有了这些分析，代码很容易写出：

第三条：获取一个十进制数字的低位部分即用源数字减去源数字低位数字清零的数。

第四条：获得一个十进制数字的高位部分即用该数字右移。