编程之美2.4
n=12时，1，11，12这3个数包含1，所以1的个数是5.
Line 9是为了防止factor溢出。
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std; int countOne(int n) {
int ans = ;
int factor = ;
while (n / factor >= ) { // avoid overflow
int high = n / factor / ;
int low = n % factor;
int current = (n / factor) % ;
if (current == ) {
ans += high * factor;
} else if (current == ) {
ans += high * factor + low + ;
} else {
ans += (high + ) * factor;
}
factor *= ;
}
if (n / factor == ) ans += (n % factor) + ;
else if (n / factor != ) ans += factor;
return ans;
} int bruteForce(int n) {
int ans = ;
for (int i = ; i <= n; ++i) {
int tmp = i;
while (tmp) {
if (tmp % == ) ans++;
tmp /= ;
}
}
return ans;
} int main() {
srand(time(NULL)); for (int i = ; i < ; ++i) {
int n = rand() % ;
int c1 = countOne(n);
int c2 = bruteForce(n);
if (c1 != c2) {
cout << c1 << " " << c2 << " " << n << endl;
}
}
return ;
}