# Sum over binary digits of integer

This might seem like a simple enough question but Mathematica seems to simplify inadequately here:
How would you sum over the digits of an arbitrary binary number?

Total[IntegerDigits[j, 2]]


which immediately simplifies to an incorrect $j+2$
In fact all

Total[IntegerDigits[j, n]]


simplify to $j+n$
After that, I tried this:

Sum[i, {i, IntegerDigits[j, 2]}]


which simplifies to another incorrect

1/2 IntegerDigits[j, 2] (1 + IntegerDigits[j, 2])


Is there any way, I can prevent these erroreous simplifications?
I need a solution that will work if I use it in another sum which, I ultimately hope, simplifies to something correct.

If you want to see what I need this for, it's for another now solved problem on Mathematics StackExchange.

• See if you can wrap it with Unevaluated
– ssch
Commented Nov 24, 2012 at 11:48
• @ssch It's hard to be sure wether Unevaluated is the reason or it's simply beyond mathematica to solve the posed problem (check the link at the end of the question) but Mathematica can't solve that then. - I tried to solve the same problem with some random cases for c(j) (refering to the link) and mathematica was able to simplify them all. With this solution now, it's stuck with two "Unevaluated"s... Commented Nov 24, 2012 at 12:07
• Have you tried j - Sum[Quotient[j, 2^k], {k, 1, IntegerLength[j, 2]}]? Commented Nov 24, 2012 at 12:35

This is no longer a problem since version 12.0. As mentioned in this document page:

Incompatible Changes since Mathematica Version 1

11.3 to 12.0

Total no longer works on expressions with an arbitrary Head.

BTW, since version 14.0, you can use DigitSum for the task:

DigitSum[j, 2] /. j -> 173
(* 5 *)


It's easy if you know what to search for. The number of ones in the binary representation of a number is known as its Hamming weight. Searching for "Hamming weight" in the Mathematica documentation leads one to the function DigitCount, which does exactly what you want:

DigitCount[j, 2, 1]
(* DigitCount[j, 2, 1] *)
% /. j -> 173
(* 5 *)

• Wish I'd thought of that. :^) Commented Nov 24, 2012 at 15:55

Following Mark's idea you could just use Tr which on a vector (simple list) returns the same thing as Total, but does not evaluate on an arbitrary head:

Tr @ IntegerDigits[j, 2] /. j -> 173

5

• You actually don't need to do @. Tr[IntegerDigits[j,2]] works too. - That being said, I'm not yet that familiar with the workings of Mathematica, once it comes to pure functions or operators like @, so maybe it's somehow advantageous to do that? Commented Nov 24, 2012 at 17:11
• @kram, Wizard here is not very fond of using many brackets, that's all. That being said, f @ x, x // f, and f[x] are three ways of saying the same thing. Commented Nov 24, 2012 at 17:14
• @J.M. Ok, that makes sense. I already knew about the // but somehow always was confused by the @. Commented Nov 24, 2012 at 17:45

I guess the issue is that Total works for arbitrary heads.

Total[h[a, b, c]]

(* Out: a + b + c *)


You could define a function that sums only lists.

listTotal[list_List] := Total[list];


Now:

Clear[j];
listTotal[IntegerDigits[j, 2]]
j = 22;
listTotal[IntegerDigits[j, 2]]

(* Out:
listTotal[IntegerDigits[j, 2]]

3
*)

• Trace shows that Total (no second argument) effectively simply applies Plus, replacing whatever head
– Rojo
Commented Nov 24, 2012 at 19:02
• @Rojo Not always.Try list = RandomInteger[{-10, 10}, {10000000}]; {AbsoluteTiming[Total[list];], AbsoluteTiming[Plus @@ list;]}. The Total version runs much faster and Trace shows no sign of Plus. If you set list=Range[10000], though, then Plus is applied. Weird, eh? Commented Nov 25, 2012 at 1:53
• I'm not sure what function you used with Rand in your last example, but it seems to not apply Plus for packed arrays. However, unless it is buggy the behaviour has to be equivalent for packed and non packed I suppose
– Rojo
Commented Nov 25, 2012 at 2:42
• @Rojo Oops, my bad. I meant list=Range[10000], which does return a packed array! Of course, the form is much more regular. Commented Nov 25, 2012 at 2:45
• Interesting. In my v8, windows, Total@Range[10000] doesn't use Plus either
– Rojo
Commented Nov 25, 2012 at 2:47

It isn't a closed form or anything, or simpler than Total[IntegerDigits[j, 2]], but here's a representation for the sum of binary digits:

$$s_2(n)=n-\sum_{k=0}^{\lfloor\log_2(n)\rfloor}\left\lfloor\frac{n}{2^{k+1}}\right\rfloor$$

or in Mathematica form,

BinaryDigitSum[n_] := n - Sum[Quotient[n, 2^k], {k, 1, IntegerLength[n, 2]}]