Problem: Number of 1 Bits
Given a number, count the number of set bits.
The 32-bit integer 11 has binary representation
so the function should return 3
To solve this problem we can keep dividing it by 2, whenever the remainder is 1, that means there is a set bit, so increment the count.
Space & Time Complexity:
Time Complexity: O(logN)
- Since each time we are diving the number by 2.
Space Complexity: O(1)
Code in C++