C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進制表示中1的個數(shù)

更新時間：2016年02月15日 16:16:11 作者：Zhang_H

這篇文章主要介紹了C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進制表示中1的個數(shù),兩道基礎的算法題目,文中也給出了解題思路,需要的朋友可以參考下

在從 1 到 n 的正數(shù)中 1 出現(xiàn)的次數(shù)

題目：

輸入一個整數(shù) n，求從 1 到 n 這 n 個整數(shù)的十進制表示中 1 出現(xiàn)的次數(shù)。

例如輸入 12，從 1 到 12 這些整數(shù)中包含 1 的數(shù)字有 1， 10， 1 1 和 12， 1 一共出現(xiàn)了 5 次

代碼實現(xiàn)（GCC編譯通過）：

#include "stdio.h"
#include "stdlib.h"
 
int count1(int n);
int count2(int n);
 
int main(void)
{
  int x;
 
  printf("輸入一個數(shù)：");
  scanf("%d",&x);
  printf("\n從0到%d一共遇到%d（%d）個1\n",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;
    //依次處理當前遍歷到的數(shù)字的各個位
    while(t != 0)
    {
        //若為1則統(tǒng)計加一
      count += (t%10 == 1)?1:0;
      t/=10;
    }
  }
   
  return count;
}
 
//解法二：
int count2(int n)
{
  int count = 0;//統(tǒng)計變量
  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開始遍歷到N，將其中的每一個數(shù)中含有“1”的個數(shù)加起來，比較好想。

方法二比較有意思，核心思路是這樣的：統(tǒng)計每一位上可能出現(xiàn)1的次數(shù)。

比如123：

個位出現(xiàn)1的數(shù)字：1,11,13,21,31，...，91,101,111,121

十位出現(xiàn)1的數(shù)字：10~19,110~119

百位出現(xiàn)1的數(shù)字：100~123

總結其中每位上1出現(xiàn)的規(guī)律即可得到方法二。其時間復雜度為O（Len），Len為數(shù)字長度

整數(shù)的二進制表示中 1 的個數(shù)
題目：整數(shù)的二進制表示中 1 的個數(shù)

要求：

輸入一個整數(shù)，求該整數(shù)的二進制表達中有多少個 1。

例如輸入 10，由于其二進制表示為 1010，有兩個 1，因此輸出 2。

分析：

解法一是普通處理方式，通過除二余二統(tǒng)計1的個數(shù)；

解法二與解法一類似，通過向右位移依次處理，每次與1按位與統(tǒng)計1的個數(shù)

解法三比較奇妙，每次將數(shù)字的最后一位處理成0，統(tǒng)計處理的次數(shù)，進而統(tǒng)計1的個數(shù)

代碼實現(xiàn)（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("輸入一個數(shù):\n");
  setbuf(stdin,NULL);
  scanf("%d",&x);
  printf("%d轉二進制中1的個數(shù)是:",x);
  printf("\n解法一：%d",count1(x));
  printf("\n解法二：%d",count2(x));
  printf("\n解法三：%d",count3(x));
   
  printf("\n");
  return 0;
}
 
//除二、余二依次統(tǒng)計每位
int count1(int x)
{
  int c=0;
  while(x)
  {
    if(x%2==1)
      c++;
    x/=2;
  }
  return c;
}
 
//向右移位，與1按位與統(tǒng)計每位
int count2(int x)
{
  int c=0;
  while(x)
  {
    c+=x & 0x1;
    x>>=1;
  }
  return c;
}
 
//每次將最后一個1處理成0，統(tǒng)計處理次數(shù)
int count3(int x)
{
  int c=0;
  while(x)
  {
    x&=(x-1);
    c++;
  }
  return c;
}

您可能感興趣的文章: