Program to find parity

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.
Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.

Algorithm: getParity(n)
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

Example:
Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1

Program:

C++

 // C++ program to find parity // of an integer # include # define bool int using namespace std;    // Function to get parity of number n. It returns 1 // if n has odd parity, and returns 0 if n has even // parity  bool getParity(unsigned int n) {     bool parity = 0;     while (n)     {         parity = !parity;         n     = n & (n - 1);     }          return parity; }    /* Driver program to test getParity() */ int main() {     unsigned int n = 7;     cout<<"Parity of no "<

C

 // C program to find parity // of an integer # include # define  bool int    /* Function to get parity of number n. It returns 1    if n has odd parity, and returns 0 if n has even    parity */ bool getParity(unsigned int n) {     bool parity = 0;     while (n)     {         parity = !parity;         n      = n & (n - 1);     }             return parity; }    /* Driver program to test getParity() */ int main() {     unsigned int n = 7;     printf("Parity of no %d = %s",  n,               (getParity(n)? "odd": "even"));            getchar();     return 0; }

Java

 // Java program to find parity // of an integer import java.util.*; import java.lang.*; import java.io.*; import java.math.BigInteger;    class GFG  {     /* Function to get parity of number n.     It returns 1 if n has odd parity, and     returns 0 if n has even parity */     static boolean getParity(int n)     {         boolean parity = false;         while(n != 0)         {             parity = !parity;             n = n & (n-1);         }         return parity;                }            /* Driver program to test getParity() */     public static void main (String[] args)     {         int n = 12;         System.out.println("Parity of no " + n + " = " +                          (getParity(n)? "odd": "even"));      } } /* This code is contributed by Amit khandelwal*/

Python3

 # Python3 code to get parity.    # Function to get parity of number n.  # It returns 1 if n has odd parity,  # and returns 0 if n has even parity def getParity( n ):     parity = 0     while n:         parity = ~parity         n = n & (n - 1)     return parity    # Driver program to test getParity() n = 7 print ("Parity of no ", n," = ",      ( "odd" if getParity(n) else "even"))    # This code is contributed by "Sharad_Bhardwaj".

/div>

C#

 // C# program to find parity of an integer using System;    class GFG {            /* Function to get parity of number n.     It returns 1 if n has odd parity, and     returns 0 if n has even parity */     static bool getParity(int n)     {         bool parity = false;         while(n != 0)         {             parity = !parity;             n = n & (n-1);         }         return parity;                }            // Driver code     public static void Main ()     {         int n = 7;         Console.Write("Parity of no " + n                   + " = " + (getParity(n)?                           "odd": "even"));      } }    // This code is contributed by nitin mittal.

PHP



Output:

Parity of no 7 = odd

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(Log n).

Uses: Parity is used in error detection and cryptography.

Compute the parity of a number using XOR and table look-up

References:
http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive – last checked on 30 May 2009.