11
$\begingroup$

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?
I already tried this:

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ See if you can wrap it with Unevaluated $\endgroup$
    – ssch
    Commented Nov 24, 2012 at 11:48
  • $\begingroup$ @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... $\endgroup$
    – kram1032
    Commented Nov 24, 2012 at 12:07
  • $\begingroup$ Have you tried j - Sum[Quotient[j, 2^k], {k, 1, IntegerLength[j, 2]}]? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Nov 24, 2012 at 12:35

5 Answers 5

Reset to default
2
$\begingroup$

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 *)

enter image description here

Improve this answer
$\endgroup$
19
$\begingroup$

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 *)
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Wish I'd thought of that. :^) $\endgroup$
    – Mr.Wizard
    Commented Nov 24, 2012 at 15:55
7
$\begingroup$

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
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – kram1032
    Commented Nov 24, 2012 at 17:11
  • 3
    $\begingroup$ @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. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Nov 24, 2012 at 17:14
  • $\begingroup$ @J.M. Ok, that makes sense. I already knew about the // but somehow always was confused by the @. $\endgroup$
    – kram1032
    Commented Nov 24, 2012 at 17:45
6
$\begingroup$

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
*)
Improve this answer
$\endgroup$
5
  • $\begingroup$ Trace shows that Total (no second argument) effectively simply applies Plus, replacing whatever head $\endgroup$
    – Rojo
    Commented Nov 24, 2012 at 19:02
  • $\begingroup$ @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? $\endgroup$
    – Mark McClure
    Commented Nov 25, 2012 at 1:53
  • $\begingroup$ 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 $\endgroup$
    – Rojo
    Commented Nov 25, 2012 at 2:42
  • $\begingroup$ @Rojo Oops, my bad. I meant list=Range[10000], which does return a packed array! Of course, the form is much more regular. $\endgroup$
    – Mark McClure
    Commented Nov 25, 2012 at 2:45
  • $\begingroup$ Interesting. In my v8, windows, Total@Range[10000] doesn't use Plus either $\endgroup$
    – Rojo
    Commented Nov 25, 2012 at 2:47
3
$\begingroup$

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]}]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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