Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
Have you seen this OEIS entry? See also the Thue-Morse sequence. –  J. M. Sep 23 '11 at 18:53
1  
this might help –  dmuir Sep 23 '11 at 19:22
1  
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. –  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 3

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.

share|improve this answer
    
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. Sep 23 '11 at 19:16
3  
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)$. –  Robert Israel Sep 23 '11 at 21:08

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

share|improve this answer
    
Would computing the Hamming weight of a number take as much effort as checking whether its Hamming weight is odd or even? –  J. M. Sep 24 '11 at 3:01

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.

share|improve this answer
2  
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. –  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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.