闲来消遣之一:任给一个自然数,统计从0开始数到这个数时1的出现次数.

   项目终于告一段落了!很好,在元旦前准时提交客户.
   不过,30号,我们还是忙到了31号凌晨.感觉经理挺负责任的.虽然大家为了赶项目，忙了一周,都身心俱累,但我们还是坚持下来了,没有任何怨言,只有解决问题后的那份欢愉.
   可以安心回家过个假期了.
   元旦放假回家闲得慌(汗,我就是劳苦命,闲不住!),刚好本本带回家,就开起来,练练手.
   想起先前在某个群里有人说起一个题目,感觉挺有意思的.由于先前项目赶,一直没有多余的心思想其它的,渐渐的忘了.正好现在想起来,真好!
  
   题目:任给一个自然数,包括0,统计从0开始数到这个数,1的出现次数.
   这个题目的解法有n多.相信很多人看了,可以列出一大摞的解决方法出来.
   我这边就说下我的思路.
   我打算按个,十,百位...这样来统计.
   比如给个数2000.
   那在千位上有1的数是1000-1999,总共1000个.
   在百位上有1的数是100-199,1100-1199,总共200个.
   在十位上有1的数是10-19,110-119,...,1910-1919总共200个.
   在个位上有1的数是1,11,21,...,1991,总共200个.
   这样一来就可以统计出一个规律了.
   对于数m--常量, n(1,10,100,...)位上1的个数k(n)=m/(10*n)*n
   这里假设m都是可以被n整除的
    要做到上面的条件,可以对m进行拆分(分治策略)
   比如2345就可以拆成2000+300+40+5,这样每个拆分的数都可以用上面的函数来统计,最后结果加起来就是了.
   代码如下(JAVA实现).

 /**
	 * 计算从1数到n的过程中1的出现次数.
	 * 
	 * @param n
	 * @return
	 */
	public long getNumbersOfOne(long n) {
		long amount = 0;
		int t = 0;
		int i = 1;
		int x = 0;
		for (; (t = new Double(n / Math.pow(10, i)).intValue()) > 0; i++) {
			// 除数
			x = new Double(Math.pow(10, i - 1)).intValue();
			amount += t * x;
			// 余数
			amount = countRemind(n, amount, i, x);
		}
		x = new Double(Math.pow(10, i - 1)).intValue();
		// 余数
		amount = countRemind(n, amount, i, x);

		return amount;
	}

	/**
	 * 计算余数中该位上1的出现次数.
	 * 
	 * @param n
	 * @param amount
	 * @param i
	 * @param x
	 * @return
	 */
	private long countRemind(long n, long amount, int i, int x) {
		int k = new Double(n % Math.pow(10, i)).intValue();
		int m = BASE * x - 1;
		if (m == 0) {
			// 个位的
			if (k >= 1)
				amount += 1;
		} else {
			int num = k - m;
			if (num >= x)
				amount += x;
			else if (num >= 0)
				amount += num;
		}
		return amount;
	}

该算法复杂度是logN级别的.
不知道大家有什么更好的解法,欢迎贴上来!