Can you write a function to count the number of bits that are set to 1 in a given number?

You could implement this using bitwise operations in many programming languages. Here is an example of how to implement this in Python:

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

You would call the function count_set_bits with the number for which you want to count the number of set bits. For example, if you want to count the number of set bits in the binary representation of the number 5 (which is 101 in binary), you would call:

print(count_set_bits(5))  # Output: 2

Explanation: The code keeps resetting the rightmost set bit of the number until there are no set bits left, and it counts the number of operations this takes. This is done through the line ‘n &= n - 1‘, which in each iteration, resets the rightmost set bit of n (subtracting 1 flips the rightmost set bit of n and all bits to the right of it, and taking bitwise-AND with n resets these flipped bits).

The time complexity of the function depends on the number of set bits in the number. If the number of set bits is b, then the runtime is O(b), because each operation removes a set bit.

For example, consider the 8-bit integer 01100100. Here’s how the operations proceed:
$$\begin{aligned} n &= 01100100\\ n-1 &= 01100011\\ n \& (n-1) &= 01100000\\ \hline n &= 01100000\\ n-1 &= 01011111\\ n \& (n-1) &= 01000000\\ \hline n &= 01000000\\ n-1 &= 00111111\\ n \& (n-1) &= 00000000\end{aligned}$$

We have to repeat the procedure three times (which is the number of set bits in the original number), so the complexity is indeed O(b).