0

So I am supposed to find the parity of a number where parity is odd if there are odd number of set bits in the binary representation of the given number and even otherwise. I have a solution but the code is not very understandable and thus am looking for an explanation to it.

int y = x ^ (x >> 1); //given number is x.
y = y ^ (y >> 2); 
y = y ^ (y >> 4); 
y = y ^ (y >> 8); 
y = y ^ (y >> 16); 
// Rightmost bit of y holds the parity value 
// if (y&1) is 1 then parity is odd else even 
if (y & 1) 
 return odd; 
return even;
Golovkin
  • 33
  • 7

1 Answers1

0

This is quite simple. This is how bits are merged to get parity bit:

Bit numbers:

0    1    2    3    4    5    6   7
 \  /      \  /      \  /     \  /
  01        23        45       56        x ^ (x >> 1)
    \      /            \     /
     \    /              \   /
      0123                4567           y ^ (y >> 2);
          \              /
           \            /
            \          /
             \        /
              01234567                   y ^ (y >> 4);

Simply this tree shows how the youngest bit is effectively evaluated. Note that there are extra pairs on each step, but they are simply do not have impact on bit which is a final result.

Marek R
  • 32,568
  • 6
  • 55
  • 140
  • This is an odd parity check, no pun intended. Parity check is a summ of odd number of bits, so 0-6, not 0-7. Calculted with parity bit whole word should return a 0 in bit 0. This code result in some strange value though. – Swift - Friday Pie Sep 16 '19 at 10:54
  • @Swift-FridayPie well it's not a parity *check*, it just computes the parity – harold Sep 16 '19 at 11:00
  • @harold it IS parity check, it calculates parity bit properly. I.e if popcount of word is even, then result is "odd". But parity value is a popcount. Popcount would take another iteration to alculate and in different way, which is not necessary for parity bit evaluation. – Swift - Friday Pie Sep 16 '19 at 11:03