in Programming

Bitwise parity compute

Summary

Bitwise parity is widely used in different purposes, recently came across the ICAO MRTD(Machine Readable Travel Documents) parity usage on calculate the DES and MAC derivation key. Get into the detail how to compute it in program.

Different Methods to Compute Bitwise Parity

Refer to this link Bit Twiddling Hacks from Stanford University to get all kinds of methods about how to deal with bitwise operation, they are really good at it.

For Bitwise Parity compute, Computing parity the naive way will lead you to different kinds of methods.

Template Methods to Compute Bitwise Parity

Below code is the implementation of template method to compute bitwise parity, regardless of the input type (char, int, long), procedure as:
1, convert the number down to a 4 bit number with same parity
2, use 0x6996 as 16 bits lookup table to get look up the bitwise parity.

// Templetised method to calculate the parity bit for any integral
// type of data. Uses the parallel parity technique as found here:
// http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive
template <typename T>
bool calcEvenParity(T value)
{
    // Note: We could place a sanity check here to ensure the data type
    // is integral (i.e. if (!std::is_integral<t>::value) { bail! } )
    // But trying to pass a non-integral type to the right-shift operator
    // results in a compile-time failure so there's really no need to.

    // Calc half the size of the type, expressed in bits
    T typeSizeInBits = sizeof(T) * 4;

    // Convert our number down to a 4-bit number with the same parity
    while (typeSizeInBits >= 4)
    {
        value ^= value >> typeSizeInBits;
        typeSizeInBits /= 2;
    }

    // Bitwise AND our value with 255
    value &= 0xf;

    // Finally, the hex value 0x6996 is the binary value: 0110 1001 1001 0110
    // This sequence of binary digits is then used as a look-up table to look-up
    // the correct parity bit is for any 4 bit number, which is exactly what we
    // have now that we've crunched our value down in the above loop! Clever!
    // An excellent explanation of how it all works can be found here:
    // http://stackoverflow.com/questions/3202745/question-from-bit-twiddling-site
    return (0x6996 >> value) & 1;
}

Interesting Bitwise XOR to Swapping without "temp"

Refer to this link The Magic of XOR, you can swap two numbers without use the "temp",

  x = x ^ y ;
  y = x ^ y ;
  x = x ^ y ;

Explained as below,

  // x == A, y == B
  x = x ^ y ;  
   // x == A ^ B, y == B
  y = x ^ y ;  
   // x == A ^ B
   // y == (A ^ B) ^ B == A ^ (B ^ B)  (by Assoc)
   //   == A ^ 0  (by z ^ z == 0 property)
   //   == A      (by z ^ 0 == z property)
  x = x ^ y ;
   // x == ( A ^ B ) ^ A
   //   == ( A ^ A ) ^ B  (by Assoc/Commutativity)
   //   == 0 ^ B            (by z ^ z == 0 property)
   //   == B                (by z ^ 0 == z property)
   // y == A

Write a Comment

Comment