Count Set Bits (Population Count)

# Count Set Bits (Population Count) ## Difficulty Easy ## Tags `bit manipulation` ## Problem Statement Given a non-negative integer `n`, count the number of 1 bits (also known as the Hamming weight or population count). ## Constraints - 0 ≤ n ≤ 2³¹ - 1 ## Signatures ### Python ```python def count_bits(n: int) -> int: pass ``` ### Java ```java public class Solution { public int count_bits(int n) { return null; } } ``` ### Csharp ```csharp public class Solution { public int count_bits(int n) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int count_bits(int n) { } }; ``` ### C ```c int count_bits(int n) { } ``` ### Ruby ```ruby def count_bits(n) end ``` ### Perl ```perl sub count_bits { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def count_bits(n: Int): Int = { } } ``` ### Haskell ```haskell count_bits :: ... -> ... count_bits args = undefined ``` ### Clojure ```clojure (defn count_bits [n] ) ``` ### Scheme ```scheme (define (count_bits n) ) ``` ## Examples ### Example 1 **Input:** ``` n = 11 ``` **Output:** ``` 3 ``` **Explanation:** 11 in binary is 1011, which has three 1 bits. ### Example 2 **Input:** ``` n = 128 ``` **Output:** ``` 1 ``` **Explanation:** 128 in binary is 10000000, which has one 1 bit. ### Example 3 **Input:** ``` n = 255 ``` **Output:** ``` 8 ``` **Explanation:** 255 in binary is 11111111, which has eight 1 bits. ### Example 4 **Input:** ``` n = 0 ``` **Output:** ``` 0 ``` ## Hints 1. **Naive approach**: Check each bit using `n & 1`, then right shift `n >>= 1`. Loop 32 times. 2. **Brian Kernighan's algorithm**: `n & (n - 1)` clears the lowest set bit. Count iterations until n becomes 0. 3. Kernighan's approach is O(k) where k is the number of set bits.