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
-
5Have you seen [this OEIS entry](http://oeis.org/A000120)? See also the [Thue-Morse sequence](http://mathworld.wolfram.com/Thue-MorseSequence.html). – 2011-09-23
-
1[this](http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel) might help – 2011-09-23
-
1Intel 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. – 2011-09-24
-
0Are your numbers given in binary to start with? – 2011-09-24
-
0To 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. – 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.
-
0This is equivalent (computationally) to counting the ones manually. Any faster relation? I want to do this many times and for big numbers ! – 2011-09-23
-
0@Tarek: Well, the Thue-Morse sequence satisfies a nice recursion relation. Have you tried it? – 2011-09-23
-
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.
-
2You 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. – 2011-09-24
-
0@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. – 2011-09-24
-
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