Last Updated: 11 Dec, 2020
Binary Numbers
Easy
Asked in company
Given a number ‘N’, you are supposed to calculate the number of 1s in the binary representation of the given number.
For example:
Given ‘N’ = 4,
Its binary representation is 0..0100, therefore there is only 1 set bit, hence the answer will be 1.
Input format:
The first line of input contains ‘T’, denoting the number of test cases. Then each test case follows.
Each test case contains a single integer ‘N’, denoting the number given.
Output Format :
For each test case, print a single line that contains a single integer that denotes the total number of 1s which satisfy the above description.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10 ^ 18
Time Limit: 1 sec.
Approaches
The idea is to check every bit in the number and maintain a counter and increase it by 1 if the bit is set.
The steps are as follows:
- Maintain a variable ‘setBits,’ which is initially 0, which will store the count of set bits.
- Execute a while loop with the condition that the number is greater than zero:
- If the current bit is set, increase ‘setBits’ by 1.
- We will right-shift the number by 1 place.
- Return ‘setBits’ as the final answer.
The idea here is subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit. So if we subtract a number by 1 and do it bitwise & with itself (‘N’ & (‘N’ - 1)), we unset the rightmost set bit. If we do ‘N’ & (‘N’ - 1) in a loop and count the number of times the loop executes, we get the set bit count.
The steps are as follows:
- Maintain a variable ‘setBits’, which is initially 0.
- Execute a while loop with the condition that the number is greater than zero:
- We will assign ‘N’ equal to ‘N’ & ( ‘N - 1’).
- We will increase variable ‘’ by 1 as we have successfully removed a ‘1’ from its binary representation.
- We will return ‘setBits’ as the final result.