这是一道比较传统的面试题，自己写了个10进制的求1个数的程序，后来在《编程之美》中发现上面的解法更好一些，随后有用它的方法重写了一遍2进制下的求解方法。

　　程序源码请点击下载。

　　对于自己写的10进制程序：主要思想还是从前期的分析得出来的：

　　1、先统计N的相应位置所对应的累加和数组

　　2、从前到后，根据所当前位置对应的位数，进行累加，即：

　　　　1）当当前为为1时，当前位置所对应的单位个数+低位数值+1；

　　　　2）当当前为为0时，用当前位置的数值*当前位置为所对应的1的单位总个数+低位数值；

　　3、求出当前位总和后，向下一位移位，递归累加

　　程序主要源码如下：

1 long long numCount[32] = {
   0}; 2 //function entrance 3 unsigned long long getDecimal(unsigned long long num) 4 { 5     unsigned long long result = 0L;  6     unsigned long long temp = num; 7     unsigned long long bNum = 10; 8     int nLength = 1; 9     //get the length of number10     while(temp /= 10)11     {12         nLength++;13     }14     //init the first one15     numCount[0] = 1;16 17     //Record the sum of the big number for pretreatment;18     for(int i = 1; i < nLength - 1; i++)19     {20         numCount[i] = bNum + (numCount[i-1] * 10);21         bNum *= 10;22     }23     result = statisticTen(num, bNum, nLength);24     return result;25 }26 /*27 * @param theNume : the number you wanna calculate 28 * @param bNum : the index of directing current number29 * @param Length : the length of theNum30 */31 int statisticTen(unsigned long long theNum, unsigned long long bNum, int Length)32 {33     //stop the recursion process34     if(Length < 2 || theNum == 0)35     {36         if(theNum != 0)37             return 1;38         else39             return 0;40     }41 42     int fn = 0;43     unsigned long long sn = 0L;44     fn = theNum / bNum;//get count of higher number45     sn = theNum % bNum;//get count of lower number46 47     unsigned long long temp = 0L;48 49     if(fn == 1) 50     {51         //we can regards numCount[Length - 2] as higher number52          temp = sn + 1 + numCount[Length - 2];53     }54     else 55     {56          temp = fn * numCount[Length - 2] + bNum;57     }58     //go to the next recursion59     return temp += statisticTen(sn, bNum/10, --Length);60 }

　　2进制程序主要是根据《编程之美》中的统计思想的重写，其中并为使用递归，效率更高，统计方法大同小异，具体推导过程，详见《编程之美》2.4节

　　程序主要代码如下：

//function entranceint statisticBin(long long theNum){    unsigned long long iCount = 0L;    unsigned int iFactor = 0;    unsigned long long iLowerNum = 0L;    unsigned int iCurrNum = 0;    unsigned long long iHigherNum = 0L;    while(theNum >> iFactor != 0)    {        iLowerNum = theNum - ((theNum >> iFactor) << iFactor);        iCurrNum = (theNum >> iFactor) & 0x01;        iHigherNum = theNum >> (iFactor + 1);        switch(iCurrNum)        {        case 0:            iCount += iHigherNum * (1 << iFactor);            break;        case 1:            iCount += iHigherNum * (1 << iFactor) + iLowerNum + 1;            break;        }        iFactor++;    }    return iCount;}

测试：

　　对于10进制，选取了f(n)=n的形式，来确定结果的正确性。

　　对于2进制，选取了111010100010101010101010这个二进制数，其结果也与期望相符。

　　如图所示：

　　

小结：

　　可以看到，虽然统计思想大同小异，但是具体实现时却大为不同，自己的程序使用了数组和递归，在时间和空间复杂度上都大不如后者，通过此题说明以下几点：

　　1、在程序的分析初期，一定要总结归纳，寻找其中的规律，为编程做好理论基础

　　2、在工程实践中，一定要摆脱大脑特定思维，从计算机效率出发来思考和解决问题。

　　3、编程是一个探索其中，也乐在其中的过程，要勤学勤练，保持正确的思考问题、解决问题的方法。