# 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 Nov 24 '12 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... –  kram1032 Nov 24 '12 at 12:07
Have you tried j - Sum[Quotient[j, 2^k], {k, 1, IntegerLength[j, 2]}]? –  Ｊ. Ｍ. Nov 24 '12 at 12:35
@J.M. That seems to do the trick! Can you add it as an answer so I can accept it? Thanks a lot! –  kram1032 Nov 24 '12 at 12:42

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. :^) –  Mr.Wizard Nov 24 '12 at 15:55

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 Nov 24 '12 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? –  Mark McClure Nov 25 '12 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 Nov 25 '12 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. –  Mark McClure Nov 25 '12 at 2:45
Interesting. In my v8, windows, Total@Range[10000] doesn't use Plus either –  Rojo Nov 25 '12 at 2:47

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? –  kram1032 Nov 24 '12 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. –  Ｊ. Ｍ. Nov 24 '12 at 17:14
@J.M. Ok, that makes sense. I already knew about the // but somehow always was confused by the @. –  kram1032 Nov 24 '12 at 17:45