Subject to a

Count the number of decimal digits represented as 1 in binary

Here’s an example:

  • When a decimal number is 1, its binary representation is 001, and the binary representation of the number of 1s is 1.
  • When the decimal number is 2, its binary representation is 010, and the binary representation of the number of 1s is 1.
  • When the decimal number is 3, its binary representation is 011, and the binary representation of 1 is 2.
  • When a decimal number is 4, its binary representation is 100 and the number of binary ones is 1.
  • When the decimal number is 5, its binary representation is 101 and the number of binary ones is 2.
  • When the decimal number is 6, its binary representation is 110 and the number of binary ones is 2.
  • When the decimal number is 7, its binary representation is 111 and the number of binary ones is 3.

Solution of time complexity O(logn)

The code that comes to mind for this problem is the following:

int count = 0;

while(n ! =0)
{
    if(n % 2= =1)
    {
        count++;
    }
    
    n = n >> 1;
}
Copy the code

The above code does two main steps:

  • n % 2Represents the modular operation of a number, that is, computationEnd of binaryIs it a 1 or a 0, if binary ends with a 1, then count increments, and count is the number of binary ones;
  • n = n >> 1Represents the binaryI’m going to go one place to the rightFor example, if the binary representation of the decimal number 7 is 111, it becomes 011 by moving it one bit to the right.

This solution can calculate the number of binary 1’s, but we can see that the time complexity of this solution is O(logn). For example, when n is 7, the binary representation is 111, it will loop three times, which is very close to the value of log base 2 of 7.

Topic 2

The program reads an integer n, assuming n is not greater than 1000. Print the number of 1s in binary representation of each digit from 1 to n.

Solution of time complexity O(nlogn)

Some friends may say, this problem two is not easy? So let’s just add a for loop to the solution above.

int main(a) 
{
	int i, j, n, count;
	
	scanf("%d", &n);
	
	for(i = 1; i <= n; i++)
	{
		j = i;
	    count = 0;
		
    	while(j ! =0)
    	{
            if(j % 2= =1)
            {
                count++;
            }
    
    		j = j >> 1;
    	}
    	
    	printf("number:%d, count:%d\n", i, count);
	}

	return 0;
}
Copy the code

Assuming input 7, output:

number:1, count:1
number:2, count:1
number:3, count:2
number:4, count:1
number:5, count:2
number:6, count:2
number:7, count:3
number:8, count:1
Copy the code

Yes, add a for loop, using the above method can solve the topic 2, it is worth encouraging, but the time complexity of the program is time complexity O (nlogn), efficiency is not high, so we must have a spirit, is to use the least time complexity to solve the problems of the algorithm, so as to progress again.

Solution of time complexity O(n)

First observe the following bit-operation properties:

y = x & (x - 1)
Copy the code

We saw that x and x minus one are bitwise and sum, so we have to think about this in binary terms.

Such as:

  • Assuming thatxIt’s 3, its binary is 011;
  • thenx - 1It’s 2, its binary is 010;
  • x & (x - 1)The binary is 010.

So x & (x-1) is actually equivalent to removing the last 1 in the binary representation of x, and we find that the y variable differs from the x variable by only one 1 in the binary representation.

If we use an array f to record the number of 1s in the binary representation of the corresponding number, then the array f[I] stores the number of 1s in the binary representation of the number I, and we can deduce that f[I] = f[I & (I – 1)] + 1, That is, the number I has one more 1 in the binary representation of the number I & (I – 1), so that in one step we get the result f[I], which is the number of 1 in the binary representation of the corresponding number.

The code is as follows:

int main(a) 
{
    int n,i;
    int f[1001];
    
    f[0] = 0;
    
    scanf("%d", &n);

    for(i = 1; i <= n; i++) 
    {
        f[i] = f[i & (i - 1)] + 1;
    }
    
    for(i = 1; i <= n; i++) 
    {
        printf("%d ", f[i]);
    }
    printf("\n");
    
    return 0;
}
Copy the code

The procedure is as follows:

  • We start by reading an integern, represents the range of required solutions;
  • Then the cyclenEvery time, every passf[i] = f[i & (i - 1)] + 1To calculate thef[i]Is the binary representation of the number of 1’s;
  • And then it prints 1 to PInEach digit in the binary represents the number of 1s in.

For this solution the time complexity of the program is O(n).