// let length is the n's bit length, base is digit in the highest bit, restNumber is the number exclude highest bit,

// the countDigitOne can be gotten by following formula.

// (1) if base == 0, the digit one number is countDigitOne(restNumber)

// (2) if base == 1, the digit one number is countDigitOne(restNumber) + pow(10, length-2)(length-1)base + (restNumber+1);

// (3) if base > 1, the digit one number is countDigitOne(restNumber) + pow(10, length-2)(length-1)base+pow(10, length-1);

// This formula can be executed by Dynamic Program. As next round's countDigitOne only depends on current round's countDigitOne, only using following variables can support this Dynamic Problem:

// (1) pow: is for pow(10, length-2)

// (2) base: keep current digit in highest bit

// (3) count: keep current round countDigitOne

// (4) restNumber: keep current round's rest number

Initial Values:

length = 2

count = n%10 > 0 ? 1 : 0;

pow = 1; Math.power(10, length-2);

base = n%10;

```
public int countDigitOne(int n) {
if (n <= 0) return 0;
if (n <= 9) return 1;
int count = n%10 > 0 ? 1 : 0;
int pow = 1;
int base = n%10;
int length = 2;
int restNumber = n%10;
while (n >= 10) {
base = (n/10)%10;
if (base == 1) count = count + pow*(length-1)*base + (restNumber+1);
if (base > 1) count = count + pow*((length-1)*base + 10);
n /= 10;
pow *= 10;
length++;
restNumber += base*pow;
}
return count;
}
```