The number of ones in a binary representation of an integer

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.