求从1到n这n个整数的十进制示意中1出现的次数

求从1到n这n个整数的十进制表示中1出现的次数

题目：

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。效率尽可能高。

例如：

f(2)=1

f(12)=5

f(20)=12

f(115)=44

解决方案：

最简单的方法是从1到n循环处理，计算每个数中1的个数，累加起来。这个效率很低。

第二种方法是累加从1到n的所有数的个位十位百位等等上面1的个数，对于32位整数运算次数不超过10次。

int numberof1(int n)
{
	int sum = 0;
	int factor = 1;
	int n2 = n;
	// remainder of n/[1|10|100|1000|...]
	// 分别表示 n%1, n%10, n%100, n%1000的余数
	int remainder = 0;
	while(n2>0)
	{
		// variable num is number of 1 in place of units, from 1 to n2
		// 变量num表示从1到n2中个位上面1的个数
		int num = (n2+9)/10;
		// variable true_num is number of 1 in place of units/tens/hundreds/thousands/...(place is determined by factor), from 1 to n
		// 变量true_num表示从1到n中factor(1/10/100/1000/...)所对应位(个位/十位/百位/千位/...)上1的个数。
		// 复杂性就在这儿。对于n，如果该位是1，要特殊处理。
		int true_num; 
		if( n2 % 10 == 1)
		{
			true_num = (num-1) * factor + remainder+1;
		}
		else
		{
			true_num = num * factor;
		}
		sum += true_num;
		n2 /= 10;
		factor *= 10;
		remainder = n % factor;
	}
	return sum;
}

大家可以手工核对，也可以使用那个稳妥但低效的办法核对。我手工核对过，应该没有问题。