How would I take multiple single bit binary numbers and convert it into a single binary array number?

Question

So lets say I have these:

101010101001

Now lets also say I didn't count them you should count binary, lets say I counted that number at 6 because their are 6 1s and the 0s don't count. Now how would I convert it into this kind of binary:

011

What logic would I use to do that?

Answer 1

This is called (by Knuth) sideways addition, and the result is the Hamming weight (or distance from $0$) of the bit string. Knuth describes efficient methods for performing sideways addition in volume 4A of The Art of Computer Programming, 7.1.3. Bitwise Tricks and Techniques. You can find a description of some of them on the Wikipedia page for Hamming weight.

The term "sideways addition" occurs (for the more general case of adding the digits in a radix $p$ representation) in a marginal note to exercise 4.24 in Concrete Mathematics by Graham, Kunth, and Patashnik (1994). I have no idea whether this is the first occurrence. By the way, the goal of that exercise is to show that the multiplicity of $p$ as prime factor in $n!$ is $$\frac{n-\nu_p(n)}{p-1}$$ where $\nu_p(n)$ is the "sideways sum" of the radix $p$ representation of $n$.