5
$\begingroup$

Is there any relation that tells whether the number of ones in a binary representation of an integer is an even or an odd number?

$\endgroup$
5
  • 5
    $\begingroup$ Have you seen this OEIS entry? See also the Thue-Morse sequence. $\endgroup$ Sep 23, 2011 at 18:53
  • 1
    $\begingroup$ this might help $\endgroup$
    – dmuir
    Sep 23, 2011 at 19:22
  • 1
    $\begingroup$ Intel x86 processors at least used to have a parity flag indicating the parity of the lowest byte (or word) of the previously affected register. You can 'fold' a longer integer into the lowest byte (or word, if that is enough) as in Esteban Crespi's answer, but you can stop at 8 bits, because the parity flag will tell you the result. $\endgroup$ Sep 24, 2011 at 12:32
  • $\begingroup$ Are your numbers given in binary to start with? $\endgroup$ Sep 24, 2011 at 12:47
  • $\begingroup$ To enhance Jyrki Lahtonen's answer, AMD's old processor manual referred to this problem as "Population count", and gave an efficient algorithm for 64 bits. So you may want to search for "population count" or look in the processor manuals for efficient implementations to work alongside folding. $\endgroup$
    – Matt Groff
    Sep 24, 2011 at 13:02

3 Answers 3

1
$\begingroup$

If you're trying to do this on a computer, you can use some of the clever algorithms here.

$\endgroup$
1
  • $\begingroup$ Would computing the Hamming weight of a number take as much effort as checking whether its Hamming weight is odd or even? $\endgroup$ Sep 24, 2011 at 3:01
0
$\begingroup$

You could take $$f(x) = (-1)^{\displaystyle \sum_{j=0}^{\lfloor \log_2(x) \rfloor} \lfloor x/2^j \rfloor}$$ for positive integers $x$. Then $f(x) = -1$ if the number of ones is odd, $1$ if it is even.

$\endgroup$
3
  • $\begingroup$ This is equivalent (computationally) to counting the ones manually. Any faster relation? I want to do this many times and for big numbers ! $\endgroup$
    – Tarek
    Sep 23, 2011 at 19:03
  • $\begingroup$ @Tarek: Well, the Thue-Morse sequence satisfies a nice recursion relation. Have you tried it? $\endgroup$ Sep 23, 2011 at 19:16
  • 3
    $\begingroup$ Since you can't specify an $n$-bit number in general without the equivalent of $n$ bits, and each bit you change changes the result, I don't see you can hope to get it faster than $O(n)$. $\endgroup$ Sep 23, 2011 at 21:08
0
$\begingroup$

Call $p(n)$ the parity of the number of 1's in the binary representation of $n$, ie $p(n) = 0$ if it is even or $p(n)=1$ if it is odd. Then if you represent your integer in base $B=2^{32}$ (or $2^{64}$ depending on the word size of your computer) as $$ a_k B^k + a_{k-1}B^{k-1} + \dots + a_0 $$ then $p(n)$ is equal to $p(b)$ where $$ b=a_k \wedge a_{k-1} \wedge \dots \wedge a_0 $$ where $\wedge$ stands for bitwise exclusive or. Now you can use the same principle to compute $$ \begin{align}b' &= b/2^{16} \wedge (b\,\mathrm{mod} \,2^{16}),\\ b'' &= b''/2^{8} \wedge (b''\,\mathrm{mod} \,2^{8}),\\ & \dots \\ b^{(5} &= b^{(4}/2^{1} \wedge (b^{(4}\,\mathrm{mod} \,2^{1}) \end{align}$$ and $p(n) = p(b) = \dots = p(b^{(5})$ so you can find $p(n)$ in $k+4$ 32-bit xors. Note that this is not better than Robert Israel's answer from the point of view of complexity, but it is probably more efficient.

$\endgroup$
3
  • 2
    $\begingroup$ You could exclusive-or (xor) the bit values down to appropriate size and then use a lookup table. A table for 16-bit values would only take up 64k and result in a 16x speedup. $\endgroup$
    – Matt Groff
    Sep 24, 2011 at 13:14
  • $\begingroup$ @Matt: Why 16x increase? I'm not sure I agree, as you are substituing a few cheap operations with table lookup which needs slow memory access and messes the cache. $\endgroup$ Sep 24, 2011 at 15:37
  • $\begingroup$ You probably know this better than I do. IIRC bitwise shifting was relatively slow at least for some versions of x86. At least in comparison to: xor al, ah; jnp @someplace. I always use a 256-entry LUT and folding to compute the Hamming weight. $\endgroup$ Sep 24, 2011 at 16:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .