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?
The number of ones in a binary representation of an integer
-
0To enhance Jyrki Lahtonen's answer, A$M$D'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. – 2011-09-24
3 Answers
If you're trying to do this on a computer, you can use some of the clever algorithms here.
-
0Would computing the Hamming weight of a number take as much effort as checking whether its Hamming weight is odd or even? – 2011-09-24
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.
-
3Since 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)$. – 2011-09-23
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.
-
0You 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. – 2011-09-24