Number of Ones

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
AppleQualcommSnapdeal Ltd.

Problem statement

You have been given an integer ‘NUM’. Your task is to find the number of bits which are ‘1’ in the binary representation of ‘NUM’.

Example:

Given ‘NUM = 9’
Binary representation of ‘9 = 1001’, so there are 2 times 1's present.
Print ‘2’ as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases.

The only line of each test case contains a single integer ‘NUM’ representing an integer whose number of bits which are ‘1’ in the binary representation you need to print.
Output Format: 
For each test case print the number of bits ‘1’ in binary representation.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10000
1 <= NUM <= 10^9

Time Limit: 1sec
Sample Input 1:
4
1
2
17
11
Sample Output 1:
1
1
2
3

Explanation Of Sample Input 1:

Test case 1:
1’s binary representation is 1. The number of bits 1 in binary representation is 1. Therefore the answer is 1.

Test case 2:
2’s binary representation is 10. The number of bits 1 in binary representation is 1. Therefore the answer is 1.

Test case 3:
17’s binary representation is 10001. The number of bits 1 in binary representation is 2. Therefore the answer is 2.

Test case 4:
11’s binary representation is 1011. The number of bits 1 in binary representation is 3. Therefore the answer is 3.
Sample Input 2:
2
15
100
Sample Output 2:
4
3

Explanation Of Sample Input 2:

Test case 1:
15’s binary representation is 1111. The number of bits 1 in binary representation is 4. Therefore the answer is 4.

Test case 2:
100’s binary representation is 1100100. The number of bits 1 in binary representation is 3. Therefore the answer is 3.
Hint

In each step check if the least significant bit is 1 and move to the next bit. 

Approaches (2)
Using Division and Modulo Operator

We will do the process till ‘NUM’ is greater than 0: 

  1. If ‘NUM’ modulo 2 is 1 signifies my least significant bit is 1.Therefore we will increase ‘ANS’ by 1 otherwise no change. We will update ‘NUM’ to ‘NUM’/2 making the next bit to the left the least significant bit.
  2. Else come out of the loop as we have counted all the bits which were 1.
  3. Return the ‘ANS’.
Time Complexity

O(log(N)), time is taken where ‘N’ is the integer in the input.

 

As in each step, we divide number by 2 until it becomes zero.

Space Complexity

O(1), constant space is used.

 

As we just need to store only the count of the number of bits which are 1.

Code Solution
(100% EXP penalty)
Number of Ones
Full screen
Console