0
$\begingroup$

I am looking for a fast algorithm to do the following task: Given $N$ numbers $a_i, i=1,..., N$, where $a_i$ can be equal to $0$ or $1$, compute the number $s \equiv \sum_{i=1}^N a_i$ in base 2. Example: $N=3$, $a_1=0,a_2=a_3=1$, $s=10$.

There is a naif algorithm to do this task: take $a_1$, then compute $a_1+a_2$ in base $2$ by adding bit-by-bit $a_2$ to $a_1$ and by taking care of the carry, then sum $a_3$ to $a_1+a_2$ in the same way, etc... until the sum $s$ is computed.

Do you know an algorithm that can do this task in a fewer number of operations than the naif algorithm? Any improvement over the naif algorithm would be fine for me.

Thank you Best, Michele

Improve this question
$\endgroup$
5
  • $\begingroup$ Take a quick peek at en.wikipedia.org/wiki/Hamming_weight $\endgroup$
    – yberman
    Sep 6, 2013 at 17:56
  • $\begingroup$ And just increasing $s$ if $a_i\neq 0$? $\endgroup$
    – Guido Kanschat
    Sep 6, 2013 at 20:44
  • $\begingroup$ Dear Yosef, thank you for your suggestion. I have looked at the Wikipedia page, but it is not clear how this can help building an algorithm ore efficient than the naive one. $\endgroup$
    – James
    Sep 6, 2013 at 21:12
  • $\begingroup$ You need to look for "binary counter". However much of the technical literature is devoted to doing as much in parallel as possible. $\endgroup$
    – Brendan McKay
    Sep 7, 2013 at 3:18
  • 2
    $\begingroup$ This belongs on stackoverflow or cstheory.stackexchange.com (probably the former). $\endgroup$
    – darij grinberg
    Sep 8, 2013 at 13:13

1 Answer 1

Reset to default
1
$\begingroup$

This seems like more of a programming question than a math question. The usual approach is to precompute a 256-element table giving the Hamming weight of the different 8-bit bytes. Then scan through your input string 1 byte at a time, looking up the weight of each byte in the table, and summing those weights.

Notice that some processors have so-called "population count" instructions that do what you're asking directly in the hardware. These come with recurring stories/urban legands that the instructions were added at the request of the US National Security Agency, which uses them to find closely matching strings for codebreaking purposes.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The OP is talking about adding bits, while you are talking about adding bytes. $\endgroup$
    – JRN
    Sep 7, 2013 at 22:40
  • $\begingroup$ He is talking about processing the bits in byte sized chunks, which can offer a constant speedup for large inputs when presented as a byte stream. $\endgroup$
    – The Masked Avenger
    Sep 7, 2013 at 23:29
  • $\begingroup$ @TheMaskedAvenger, thanks for the clarification. The question is now why use bytes, and not, say nybbles or other word sizes. $\endgroup$
    – JRN
    Sep 8, 2013 at 0:59
  • $\begingroup$ The answer is that it depends how much memory you are willing to trade for how much speed gain. Even in embedded systems, using a kilobyte as a scratch pad to speed up computations by a factor of 8 is reasonable; using 64 Kbytes may not be. $\endgroup$
    – The Masked Avenger
    Sep 8, 2013 at 1:17
  • $\begingroup$ Hello, my question is a question about the best existing algorithm, it is not about how to program it: Suppose that any logical operation between two boolean variables A and B (A & B, A ^ B, ...) is the basic operation taking one unit of time. What is the algorithm doing the task with the smallest time? $\endgroup$
    – James
    Sep 10, 2013 at 17:50

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