int parity(int val) {
     val^=val>>8;
     val^=val>>4;
     val^=val>>2;
     val^=val>>1;
     return val&1;
 };