Number of Digit One

要点：从低到高每一位累加，需要highbits，lowbits，base。基本的rule是每隔base会有1个one，一共多少个base？有3种情况>1, ==1, <1。>1有highbits+1，<1有highbits，==1有highbits还要加上lowbits+1

图

另一个重点是highbits，lowbits，curbit和base的关系：base是从1开始，和curbit是对应的。所以highbits是curbit左边的数，所以要/(base*10)。lowbits是右边的数，所以%base（所以在个位为%1==0）。curbit就是/base%10

错误点：

• loop invariant是n/base>0，而不是n
• highbits/lowbits/curbit要在loop内更新

class Solution(object):    def countDigitOne(self, n):        """        :type n: int        :rtype: int        """        base = 1        count = 0        while n/base>0:            highbits = n//(base*10)            lowbits = n%base            curbit = n%(base*10)//base            if curbit<1:                count+=highbits*base            elif curbit==1:                count+=highbits*base+lowbits+1            elif curbit>1:                count+=(highbits+1)*base            base*=10                return count