【微软面试题】请计算出1的个数
原题目：
给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。
例如：
N=2，写下1，2。这样只出现了1个"1"
N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5
请写出一个函数，返回1到N之间出现"1"的个数，比如 f(12)=5

大家发散下，看看到底有多少种算法吧。注意复杂度O(∩_∩)O


[解决办法]
我这个程序是输出从1到N，所有的数字的个数。包括1的个数。但是这个程序现在计算0的个数是不正确的。现在确保思路没有问题。

C/C++ code

#include<iostream>#include<cmath>using namespace std;struct T{    int bit[10];};void plus(T& a,const T& b,const int k){    for(int i=0;i<10;i++)        a.bit[i]+=b.bit[i]*k;}int main(){    int i,j,k,r,w,z,n,mask;    T a[10];    T ans;    for(i=0;i<10;i++){        k=n=i-2>0?i-2:0;        for(j=0;j<n;j++)            k=k*10+8;        if(i>1)a[i].bit[0]=k*10+9;        else a[i].bit[0]=0;        for(j=1;j<=9;j++)            a[i].bit[j]=i*pow(10,i-1);    }    while(cin>>n && n){        for(i=0;i<10;i++)ans.bit[i]=0;        mask=100000000;//10^9        i=9;        while(n/mask==0){            mask/=10;            i--;        }        z=0;        while(n){            i--;            k=n/mask;            n=n%mask;            mask/=10;            if(k==0){                z++;                continue;            }            if(z!=0){                if(mask==0)ans.bit[0]+=z*k;                else ans.bit[0]+=z*k*mask*10+n;                z=0;            }            plus(ans,a[i],k);            for(j=1;j<k;j++)                if(mask)ans.bit[j]+=mask*10-1;            ans.bit[k]+=n;            for(j=1;j<=k;j++)                ans.bit[j]++;            ans.bit[0]+=i*k;                        r=0;            w=9;            for(j=i-2;j>0;j--){                r+=w*j;                w=w*10;            }            ans.bit[0]+=r*k;                    }        for(i=0;i<10;i++)            cout<<ans.bit[i]<<endl;        cout<<endl;    }    return 0;}
[解决办法]
//效率最低的一种算法：O(n^2)
C/C++ code
#include <iostream>#include <string>int main(){    int num = 0;    cout << "Please input a dec num:" ;    cin >> num;    int total = 0;    for(int i = 1; i <= num; i++)    {        int value = i;                while(value > 0)        {            int single = value % 10;            if(single == 1)                total ++;            value /= 10;            }    }    cout << num << " include 1 total :" << total << endl;    return 0;}
[解决办法]
探讨

这个是msra的原题 
http://www.msra.cn/Articles/ArticleItem.aspx?Guid=8ae08db5-e059-44bf-9181-83d40a67dadb

[解决办法]
1.利用 x & (x-1)的性质
2.利用位操作进行加法(有不同效率的实现)
3.打表
[解决办法]
探讨

引用:
1.利用 x & (x-1)的性质 
2.利用位操作进行加法(有不同效率的实现) 
3.打表 
 

打表是什么意思啊？：）

[解决办法]
探讨

我在20楼的时候指出了简单巧妙的解法的.