C++は1からnの中で1の出現の回数と数のバイナリが中の1の個数を表すことを求めます

1からnまでの正数のうち1が現れる回数
タイトル:
1つの整数nを入力し、1からnまでのn個の整数の10進数表現のうち1が現れる回数を求める.
たとえば12を入力すると、1から12までの整数に1を含む数字が1、10、1、12で、1は全部で5回出てきます
コード実装(GCCコンパイルパス):

#include "stdio.h"
#include "stdlib.h"
 
int count1(int n);
int count2(int n);
 
int main(void)
{
  int x;
 
  printf("     ：");
  scanf("%d",&x);
  printf("
 0 %d    %d（%d） 1
",x,count1(x),count2(x));
   
  return 0;
}
 
//   
int count1(int n)
{
  int count = 0;
  int i,t;
   
  //  1 n
  for(i=1;i<=n;i++)
  {
    t=i;
    //                
    while(t != 0)
    {
        //  1     
      count += (t%10 == 1)?1:0;
      t/=10;
    }
  }
   
  return count;
}
 
//   ：
int count2(int n)
{
  int count = 0;//    
  int factor = 1;//    
  int lower = 0;//          
  int higher = 0;//          
  int curr =0;//     
   
  while(n/factor != 0)
  {
    lower = n - n/factor*factor;//    
    curr = (n/factor)%10;//    
    higher = n/(factor*10);//   
     
    switch(curr)
    {
      case 0:
        count += higher * factor;
        break;
      case 1:
        count += higher * factor + lower + 1;
        break;
      default:
        count += (higher+1)*factor;
    }
     
    factor *= 10;
  }
   
  return count;
}

分析:
方法1つは、1からNまで遍歴して、その中のそれぞれの数に「1」が含まれている個数を加算して、比較的に考えたいことです.
方法2は比較的に面白くて、核心の構想はこのようにです:1位ごとに1の回数が現れる可能性があることを統計します.
例えば123:
1,11,13,21,31,...,91,101,111,121
10位に1の数字が現れる:10~19110~119
100位に1の数字が現れる:100~123
その中の各上位1に現れる法則をまとめると方法2が得られる.その時間的複雑さはO(Len),Lenはデジタル長である.
整数のバイナリ表現の中の1の個数のテーマ:整数のバイナリ表現の中の1の個数
要件:
整数を入力して、その整数のバイナリ表現の中でどれだけの1があるかを求めます.
例えば入力10は、そのバイナリ表現が1010であり、2つの1があるため、出力2である.
分析:
解法1は普通の処理方式で、二余二を除いて1の個数を統計する.
解法2は解法と同様に右シフトで順次処理し,毎回1ビットと統計1の個数
解法3は奇妙で、数字の最後のビットを0に処理するたびに、処理の回数を統計し、さらに1の個数を統計する.
コード実装(GCCコンパイルパス):

#include "stdio.h"
#include "stdlib.h"
 
int count1(int x);
int count2(int x);
int count3(int x);
 
int main(void)
{
  int x;
  printf("     :
");
  setbuf(stdin,NULL);
  scanf("%d",&x);
  printf("%d     1    :",x);
  printf("
   ：%d",count1(x));
  printf("
   ：%d",count2(x));
  printf("
   ：%d",count3(x));
   
  printf("
");
  return 0;
}
 
//  、        
int count1(int x)
{
  int c=0;
  while(x)
  {
    if(x%2==1)
      c++;
    x/=2;
  }
  return c;
}
 
//    ， 1       
int count2(int x)
{
  int c=0;
  while(x)
  {
    c+=x & 0x1;
    x>>=1;
  }
  return c;
}
 
//       1   0，      
int count3(int x)
{
  int c=0;
  while(x)
  {
    x&=(x-1);
    c++;
  }
  return c;
}