Last Updated: 13 Mar, 2021
Number of Ones
Easy
Asked in companies
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.
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
Approaches
We will do the process till ‘NUM’ is greater than 0:
- 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.
- Else come out of the loop as we have counted all the bits which were 1.
- Return the ‘ANS’.
Approach: Instead of checking every bit of the number, we can repeatedly flip the least significant bit which is ‘1’ to ‘0’. Each time this thing happens we increase ‘ANS’ by 1. The reason this algorithm works is each time it runs it only flips the least significant bit which is 1. Therefore each time it runs it makes 1 bit ‘1’ into zero. Our answer will be the total number of times it runs before ‘NUM’ becomes zero.
We can do it as follows:
- If ‘A’ is greater than zero we increase ‘ANS’ by 1 and flip the least significant bit which is 1 by updating ‘NUM’ to ‘NUM & (NUM - 1)’.
- Else come out of the loop as we have counted all the bits which were 1.
- Return the ‘ANS’.