C++ find the number of times 1 appears from 1 to n and the number of 1 in the binary representation of the number

The number of times 1 occurs in positive Numbers from 1 to n

Topic:

Enter an integer, n, and find the number of occurrences of 1 in the hexadecimal representation of the n integers from 1 to n.

For example, enter 12, and the integers from 1 to 12 that contain 1   are 1, 10, 1, and 12, 1, 1, 5 times

Code implementation (GCC was compiled and passed) :

#include "stdio.h"
#include "stdlib.h"
 
int count1(int n);
int count2(int n);
 
int main(void)
{
  int x;
 
  printf(" The input 1 The number: ");
  scanf("%d",&x);
  printf("\n from 0 to %d1 A total of encounter %d ( %d ) a 1\n",x,count1(x),count2(x));
   
  return 0;
}
 
// solution 1
int count1(int n)
{
  int count = 0;
  int i,t;
   
  // traverse 1 to n
  for(i=1;i<=n;i++)
  {
    t=i;
    // Handles the digits of the currently traversed digits in turn 
    while(t != 0)
    {
        // if 1 The statistics and 1
      count += (t%10 == 1)?1:0;
      t/=10;
    }
  }
   
  return count;
}
 
// solution 2 : 
int count2(int n)
{
  int count = 0;// Statistical variables 
  int factor = 1;// Decomposition factor 
  int lower = 0;// All the low bits currently being processed 
  int higher = 0;// All high positions of the current processing bit 
  int curr =0;// Current processing bit 
   
  while(n/factor != 0)
  {
    lower = n - n/factor*factor;// For low 
    curr = (n/factor)%10;// For the current position 
    higher = n/(factor*10);// Strives for the high 
     
    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;
}

Analysis:

Method 1 is to traverse from 1 to N, adding up the number of "1" in each of them.

Method 2 is interesting. The idea goes like this: count the number of possible 1's per bit.

Such as the 123:

1,11,13,21,31,... , 91101111121,

10 digits of 1:10~19,110~119

Numbers with 1 in the hundreds digit: 100~123

Method 2 can be obtained by summing up the rule of the occurrence of each top 1. Its time complexity is O (Len), and Len is the length of the number

The number of 1's in the base 2 representation of an integer
Title: the number of 1's in the base 2 representation of an integer

Requirements:

Enter an integer and figure out how many 1's are in the base 2 representation of the integer.

For example, input 10, since its base 2 representation is 1010, has two ones, so output 2.

Analysis:

Solution 1 is a common processing method, and the number of 1 is counted by dividing 2 by 2.

Solution 2 is similar to solution 1, which is processed in turn by rightward displacement

Solution 3 is more wonderful, each time the last digit of the number into 0, the number of statistics processing, and then the number of statistics 1

Code implementation (GCC was compiled and passed) :

#include "stdio.h"
#include "stdlib.h"
 
int count1(int x);
int count2(int x);
int count3(int x);
 
int main(void)
{
  int x;
  printf(" The input 1 The number of :\n");
  setbuf(stdin,NULL);
  scanf("%d",&x);
  printf("%d turn 2 In the system 1 The number of is :",x);
  printf("\n solution 1 : %d",count1(x));
  printf("\n solution 2 : %d",count2(x));
  printf("\n solution 3 : %d",count3(x));
   
  printf("\n");
  return 0;
}
 
// In addition to 2.  yu 2 Count each in turn 
int count1(int x)
{
  int c=0;
  while(x)
  {
    if(x%2==1)
      c++;
    x/=2;
  }
  return c;
}
 
// It's shifted to the right 1 Place by place and count each 
int count2(int x)
{
  int c=0;
  while(x)
  {
    c+=x & 0x1;
    x>>=1;
  }
  return c;
}
 
// Every time at the end 1 a 1 Processing into 0 And count the processing times 
int count3(int x)
{
  int c=0;
  while(x)
  {
    x&=(x-1);
    c++;
  }
  return c;
}