手撕代码：统计1到n二进制数中1出现的总次数

题目描述：

互娱手撕代码题。

统计从1到n这n个数的二进制表示中1出现的次数。

思路分析：

思路一：直接的做法是从1遍历到n，对于每个数和1做与操作，之后，对于这个数不断做右移操作，不断和1做与操作，直到当前数为0。这样的算法复杂度为O(nlogn)。

思路二：优化时间复杂度，那么考虑用空间换时间。利用n&(n-1)这个操作可以去掉末尾的1。利用递推f(n) = 1+f(n&(n-1))。这样就是利用空间来换时间，时间复杂度为O(n)。

代码：

思路一：

 int numZeros(int n)

 {

     int res=;

     for(int i=; i<=n; i++)

     {

         while(i>)

         {

             if(i&==)

                 res++;

             i = i>>;

          }

     }

     return res;

 }

思路二：

 int numZeros(int n)

 {

     vector<int>f(n+, );

     int res=;

     for(int i=; i<=n; i++)

     {

         f[i] = +f[i&(i-)];

         res += f[i];

     }

     return res;

 }

巴特西

手撕代码：统计1到n二进制数中1出现的总次数

最新文章

热门文章