Write a C program to find the parity of an unsigned integer | GeeksforGeeks

Write a C program to find the parity of an unsigned integer | GeeksforGeeks
Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.
We don't need the count of odd or even bit, just invert between true/false when hit one bit set.

1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

bool getParity(unsigned int n)

{

    bool parity = 0;

    while (n)

    {

        parity = !parity;

        n      = n & (n - 1);

    }       

    return parity;

}

Above solution can be optimized by using lookup table. Please refer to Bit Twiddle Hacks[1st reference] for details.

Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).

Uses: Parity is used in error detection and cryptography.

https://github.com/rgehring/EPI-book-java/blob/master/c5/P1.java
http://mindprod.com/jgloss/parity.html

    private static boolean isOddParity( final byte b )
        {
        int bb = b;
        int bitCount = 0;
        // Process bits right to left, shifting each bit in turn into the lsb position.
        for ( int i = 0; i < 8; i++, bb >>>= 1 )
            {
            if ( ( bb & 1 ) != 0 )
                {
                bitCount++;
                }
            }
        return ( bitCount & 1 ) != 0;
        }

     * Calculate parity of a single byte, using Eric Sosman's xor method
     * @return true of if odd parity, false if even parity
     */
    private static boolean isOddParityViaSosman( final byte b )
        {
        final int bb = b & 0xff;
        int parity = bb ^ ( bb >> 4 );
        parity ^= parity >> 2;
        parity ^= parity >> 1;
        return ( parity & 1 ) != 0;
        }

http://preciseinfo.org/Convert/Articles_Java/Device_Experts/Java-Device-Experts-090805052638.html

Counting bits set, in parallel
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
Read full article from Write a C program to find the parity of an unsigned integer | GeeksforGeeks