参考前人的统计思想:分别统计个、十、百、、、亿等第N位上1出现的次数。
如ABCDE,在统计D位1出现的次数时,用D做分割符,ABC为Before,E为After。
分情况考虑:(n为D的length-1)
当D = 0 时,count = Before * 10^n ;
当D = 1 时,count = Before * 10^n + After;
当D > 1 时,count = (Before + 1)*10^n;
例如:
19X8
统计X上1的次数:
1)X = 0 ,即1908 X为1的数有001x~181x,x取0~9则19为Before,8为After
此时count = 19 * 10^1 ;
2)X = 1 ,即1918 X为1的数有001x~181x,x取0~9;另外,1910~1918,则19为Before,8为After
此时count = 19 * 10^1 + (8 + 1);
3)X > 1 ,如1928 X为1的数有001x~191x,x取0~9则19为Before,8为After
此时count = (19 + 1) * 10^1 ;
特别当X在最左端时Before 为 0,最右端时After 为0
#include <stdio.h>int Count1(int n)
{
int count = ,//1出现总次数
bitCount = ,//某位1出现次数
base = ,//基数
before = n,after = , //从最右开始,则Before = n,After = 0
bitN = ;//第N位数
while(before)//向左移,还有数时循环
{
after = n % base;
before = n / (base * );
bitN = (n / base) % ;
if(bitN > )
{
bitCount = (before + ) * base;
}
else if(bitN == )
{
bitCount = (before) * base;
}
else
{
bitCount = (before) * base + (after + );
}
base *= ;
count += bitCount;
}
return count;
}int main() {
int n = ;
printf("%d\n",Count1(n));
return ;
}