整数中1出现的次数（从1到n整数中1出现的次数）

题目描述
求出1_{13的整数中1出现的次数,并算出100}1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

按位来求

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        def find(n, x):
            res = 0
            # loop from end to start
            for i in range(1, 1+len(str(n))):
                hi  = n / 10**i                 # value higher than index i
                cur = n % 10**i / 10**(i-1)     # current bit
                lo  = n % 10**i % 10**(i-1)     # value lower than index i
                
                if cur==x:  
                    res += hi*10**(i-1) + lo+1
                elif cur<x:
                    res += hi*10**(i-1)
                else:
                    res += (hi+1)*10**(i-1)
                
            return res
        
        return find(n, 1)