What is the distribution of bit counts of a binomial random variable? Suppose I have a binomial random variable $X \sim B(n,p)$ and I apply the following bit counting operation $$Y = \operatorname{bit\_count}(X)$$
where $\operatorname{bit\_count}$ is defined in the following Python code.
def bit_count(x:int) -> int:
    bits = 0
    while x:
        bits += x & 1
        x >>= 1
    return bits

Here is a table of values computing this function on $x \in [0, 19]$ (for your copy-pasting convenience).




X
bit_count(X)




0
0


1
1


2
1


3
2


4
1


5
2


6
2


7
3


8
1


9
2


10
2


11
3


12
2


13
3


14
3


15
4


16
1


17
2


18
2


19
3




Similarly, we can plot such data for $x \in [0, 49]$ to reveal a serrated pattern:

We can also consider a simulated example that gives us a sense of what the resulting distribution can look like. This was $10^4$ samples from $B(100, 0.5)$, then transformed with the $\operatorname{bit\_count}$ transform.

Because the smoothness does not apply here, we cannot consider the derivative or Jacobian for the change in variable.
How can we derive such a distribution?

We have a well-known distribution $X \sim B(n,p)$, i.e. we know $p(x)$, and a well-defined function bit_count: $x\to y$ for the domain $x\in [0:n]$. Then, the distribution over the image of bit_count is simply obtained as
$$
p(y) = \sum_{x,\; bit\_count(x) = y} p(x).
$$
