So lets say I have these:


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:


What logic would I use to do that?


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$.

| cite | improve this answer | |
  • $\begingroup$ Man I've GOT to get ahold of those books and spend some time on them. Can't wait for the rest of the volumes to get published. :-) $\endgroup$ – Fixed Point Mar 13 '13 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.