C++求1到n中1湧現的次數和數的二進制表現中1的個數

C++求1到n中1湧現的次數和數的二進制表現中1的個數。本站提示廣大學習愛好者：（C++求1到n中1湧現的次數和數的二進制表現中1的個數）文章只能為提供參考，不一定能成為您想要的結果。以下是C++求1到n中1湧現的次數和數的二進制表現中1的個數正文

在從 1 到 n 的負數中 1 湧現的次數

標題：

輸出一個整數 n，求從 1 到 n 這 n 個整數的十進制表現中 1 湧現的次數。

例如輸出 12，從 1 到 12 這些整數中包括 1  的數字有 1， 10， 1 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("\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;
    //順次處置以後遍歷到的數字的各個位
    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開端遍歷到N，將個中的每個數中含有“1”的個數加起來，比擬好想。

辦法二比擬成心思，焦點思緒是如許的：統計每位上能夠湧現1的次數。

好比123：

個位湧現1的數字：1,11,13,21,31，...，91,101,111,121

十位湧現1的數字：10~19,110~119

百位湧現1的數字：100~123

總結個中每位上1湧現的紀律便可獲得辦法二。當時間龐雜度為O（Len），Len為數字長度

整數的二進制表現中 1 的個數
標題：整數的二進制表現中 1 的個數

請求：

輸出一個整數，求該整數的二進制表達中有若干個 1。

例如輸出 10，因為其二進制表現為 1010，有兩個 1，是以輸入 2。

剖析：

解法一是通俗處置方法，經由過程除二余二統計1的個數；

解法二與解法一相似，經由過程向右位移順次處置，每次與1按位與統計1的個數

解法三比擬奧妙，每次將數字的最初一名處置成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("輸出一個數:\n");
  setbuf(stdin,NULL);
  scanf("%d",&x);
  printf("%d轉二進制中1的個數是:",x);
  printf("\n解法一：%d",count1(x));
  printf("\n解法二：%d",count2(x));
  printf("\n解法三：%d",count3(x));
   
  printf("\n");
  return 0;
}
 
//除2、余二順次統計每位
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;
}