The question here is , you need to get an unsigned integer (e.g 7). Then this integer has an binary values as ' 0111 '. Hence the number of one is ' 3 ' . The output to your program should be ' 3 ' .
Ans:
The solution to this problem is very simple. Two main operators are to be used . One is ' % ' - mod operator and the other one is ' >> ' bit-wise operator.
Bitwise operator is used to shift the bit by one place right ( >> ) or left ( << ) .
For e.g , num = 7 >> 1 , then the value assigned to num will be 3.
This can be illustrated as 7 = 0111 , then shifting bit one place right gives ' 0011 ' = 3 ;
Hence,
int num_of_ones( ){
unsigned int num , ones =0 ;
printf ( " \n Enter the number: " ) ;
scanf ( " %d ", &num );
while ( num ) { // till num not equal to zero
if ( ( num % 2 ) = = 1 )
ones++ ;
num = num >> 1;
}
printf ( " \n Ones = %d ", ones);
}
This produce the required result. But the cost of MOD ( % ) operation is high. Hence an alternative operator can be used to reduce the cost. The logical operator ( logical AND ) can be used to reduce the cost.
int num_of_ones( ){
unsigned int num , ones =0 ;
printf ( " \n Enter the number: " ) ;
scanf ( " %d ", &num );
while ( num ) { // till num not equal to zero
if ( ( num & 1 ) = = 1 )
ones++ ;
num = num >> 1;
}
printf ( " \n Ones = %d ", ones);
}
This program reduces the cost in greater amount.
But still i need to reduce the time complexity.
This program executes at O ( n ) , where n = no: of bits in the input number ( e.g 8 = ' 1000 ' => n = 4 ).
Now i need to execute the program at O ( m ), where m = no. of ones in the input number ( e.g 8 = '1000' => m = 1 );
This can be performed by
int num_of_ones( ){
unsigned int num , ones =0 ;
printf ( " \n Enter the number: " ) ;
scanf ( " %d ", &num );
while ( num ) { // till num not equal to zero
num = num & ( num - 1 );
ones++;
}
printf ( " \n Ones = %d ", ones);
}
For e.g , if num=8 , then at line 6,
num = num & ( num - 1 )
num = 8 & 7 --------------> 1 0 0 0
0 1 1 1 (&)
= 0 0 0 0
Hence the loop executes only one time.
If you have better idea, please post in comment.
Categories:
program questions
