Coding Interview PatternsNumber of 1 Bits
EasyBitwise Manipulation
Number of 1 Bits
Explanation & Solution
Description
Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the [Hamming weight](https://en.wikipedia.org/wiki/Hamming_weight)).
Input: n = 11
Output: 3
Explanation: The input binary string 1011 has a total of three set bits.
Constraints
1 <= n <= 2^31 - 1
Approach
Bitwise Manipulation pattern
Key Insight
- Instead of checking every bit (32 iterations), we only iterate once per set bit
- This makes the algorithm O(k) where k is the number of set bits, rather than O(32)
- Time: O(k) where k = number of set bits | Space: O(1)