每日一题：给定n， 求出小于n的所有数中1的位数

每日一题：给定n， 求出小于n的所有数中1的位数

---

问题描述：给定整数 n，要求编写函数f，返回[1, n]中所有数中1的位数。例如，如果f输入10的话，函数返回2，其中1中含有一个1，10中含有一个1.

---

思路：这里首先想到的是对于给定一个整数 i，如果分解出i的各个数位。这个算法是比较简单的，取模10，然后除10即可。实现的代码如下：

// 这个函数直接输入的顺序和原来的数字
// 相反的，下面使用递归的形式正序输出
void integer2Bit(int i)
{
    while(i > 0)
    {
        printf("%d", i % 10);
        i = i / 10;
    }
}
// 递归版本，如果函数输入123456，函数
// 输出123456
 void integer2Bit_recursive(int i)
 {
     // 函数的出口条件
    if( (i >= 0) && (i <= 9) )
    {
        printf("%d, ", i);
    }
    else
    {
       integer2Bit_recursive(i / 10);
       printf("%d, ", i % 10);
    }
 }

取出各位之后，判断各位是否是1即可实现。

---

实现代码：

#include <stdio.h>
#include <stdlib.h>
// 给定一个i，然后返回i中数字1的个数，比如
// 1251返回的是2
int countTotal1Nums(int i)
{
    int count = 0;
    while(i > 0)
    {
        if ((i % 10) == 1)
        {
            ++count;
        }
        i = i / 10;
    }
    return count;
}
// 给定一个数n，该函数返回的是[1, n]中n个数中
// 所有1的个数
 int count(int n)
 {
     int total = 0;
     int i;
     for(i = 1; i <= n; ++i)
     {
        total += countTotal1Nums(i);
     }
     return total;
 }
int main()
{
    // 下面是测试程序
    // 2
    printf("n = %d, and the result is %d/n", 10, count(10));
    return 0;
}