Chapter 5 : Problem 1

Chapter_5_1

#include <iostream>
using namespace std;

/* Code to generate a LUT for parity */
short computeParity( short num )
{
  short parity = 0;
  while (num > 0)
  {
    parity ^= (x&1);
    x >>= 1;
  }
  return parity;
}

/*
The while loop in the compute parity can be optimized by just unsetting the last possible 1 bit set
That way even though the complexity is still at O(N) where N is the size of bits in short integer type~ 16 we
still optimize to only loop the number of times a bit is set:

while (num > 0)
{
  parity ^= 1;
  x &= (x - 1)   // This unsets the last bit
}


*/

int main (int argc, char *argv[])
{
  parityLUT[0x10000];
  
  //First make sure you populate the LUT for parity. We could provide a static table. But I am lazy.
  for (short i = 0; i <= 0xFFFF; i++)
  {
    parityLUT[i] = computeParity(i);  // Compute the parity of all values from 0 to 0xFFFF
  }
  
  // Now that we have ourself the table we can calculate the parity of the actual 64 bit number.
  unsigned long num;
  cin<<num;
  
  // We now need to break down the 64 bit long into smaller 16 bit parts
  unsigned short finalParity = 0;
  
  finalParity = parityLUT[ (num & 0xFFFF)] ^ parityLUT[(num >> 16) & 0xFFFF] ^ parityLUT[(num >> 32) & 0xFFFF] ^ parityLUT[(num >> 56)];
  
  cout<<"The final parity value is " + finalParity;
  return 0;
}