4
$\begingroup$

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?

  • 5
    Have 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 help2011-09-23
  • 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.2011-09-24
  • 0
    Are your numbers given in binary to start with?2011-09-24
  • 0
    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.2011-09-24

3 Answers 3