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?
Asked
Active
Viewed 4,628 times
5
-
5Have you seen this OEIS entry? See also the Thue-Morse sequence. – J. M. ain't a mathematician Sep 23 '11 at 18:53
-
1this might help – dmuir Sep 23 '11 at 19:22
-
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. – Jyrki Lahtonen Sep 24 '11 at 12:32
-
Are your numbers given in binary to start with? – Christian Blatter Sep 24 '11 at 12:47
-
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. – Matt Groff Sep 24 '11 at 13:02
3 Answers
1
If you're trying to do this on a computer, you can use some of the clever algorithms here.
Joshua Green
- 11
-
Would computing the Hamming weight of a number take as much effort as checking whether its Hamming weight is odd or even? – J. M. ain't a mathematician Sep 24 '11 at 03:01
0
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.
Robert Israel
- 448,999
-
This is equivalent (computationally) to counting the ones manually. Any faster relation? I want to do this many times and for big numbers ! – Tarek Sep 23 '11 at 19:03
-
@Tarek: Well, the Thue-Morse sequence satisfies a nice recursion relation. Have you tried it? – J. M. ain't a mathematician Sep 23 '11 at 19:16
-
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)$. – Robert Israel Sep 23 '11 at 21:08
0
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.
Esteban Crespi
- 4,007
-
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. – Matt Groff Sep 24 '11 at 13:14
-
@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. – Esteban Crespi Sep 24 '11 at 15:37
-
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. – Jyrki Lahtonen Sep 24 '11 at 16:37