Count Bits - Implementation

Here's the complete solution using Brian Kernighan's algorithm:

function countBits(n)
    count := 0
    while n > 0
        n := n & (n - 1)    // Clear rightmost set bit
        count := count + 1
    return count

Each iteration clears one set bit. The loop runs exactly as many times as there are 1s in $n$. Time complexity: $O(k)$ where $k$ is the number of set bits. Space complexity: $O(1)$.