C++ program to find parity of a number efficiently

In this tutorial, we are going to learn how to find parity of a number efficiently in C++. Here we will learn about the parity of a number, algorithm to find the parity of a number efficiently, and after that, we will see the C++ program for the same.

Parity of a number

Parity of a number is a term used to tell that the total number of set bits(1’s) in its binary representation is even or odd. It is of two types:-
1. Even Parity: If the total number of set bits (1’s) is even, then that number has even parity.
2. Odd Parity: If the total number of set bits (1’s) is odd, then that number has odd parity.
For example:-
12 has even parity because it has an even number of set bits in its binary representation i.e ‘1100’.
14 has odd parity because it has an odd number of set bits in its binary representation i.e ‘1110’.

Efficient Algorithm to find parity of a number

The most efficient way of finding the parity of a number is by using XOR and shifting operator as shown below.
b = n ^ (n >> 1);
b = b ^ (b >> 2);
b = b ^ (b >> 4);
b = b ^ (b >> 8);
b = b ^ (b >> 16);

In the above operations, we use XOR and left shift operator. We are shifting double bits of the previous operation. And taking the XOR with that number. We know that 0 XOR 1 or 1 XOR 0 is 1, otherwise 0. So when we divide the binary representation of a number into two equal halves by length & we do XOR between them, all different pairs of bits result into set bits in the result number i.e “b” here.

Now, after the above operations b contain the rightmost bit of b and represent the parity of n. If the rightmost bit is 1, then n will have odd parity and if it is 0 then n will have even parity.
We check the odd or even by using bitwise AND operator. If (b & 1) is true means odd else even.

C++ program to find parity of a number efficiently

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h>
using namespace std; 

/*===============================================
FUNCTION TO COUNT NO. OF CLUMPS IN GIVEN ARRAY
================================================*/
int check_parity(int n) 
{
    int b;
    //Left Shifting by double of previous operation shift
    //And take xor with the previous result.
    b = n ^ (n >> 1); 
    b = b ^ (b >> 2); 
    b = b ^ (b >> 4); 
    b = b ^ (b >> 8); 
    b = b ^ (b >> 16); 

    //Now b contain the parity value
    //If b is odd mean odd parity else even parity
    if (b & 1) //This is used for checking odd
        return 1; 
    else      
        return 0; 
} 

/*======================================
   MAIN FUNCTION
=======================================*/
int main() 
{ 
    //Initialising variable n
    int n=14;
    //Calling function check_parity
    int ans=check_parity(n);
    //check if ans==0 -->even parity
    if(ans==0)
        cout<<"Even Parity"<<endl;
    else
        cout<<"Odd Parity"<<endl;
    return 0; 
} 

Output:-

Odd Parity

Thanks for reading this tutorial. I hope it helps you !!

Leave a Reply

Your email address will not be published. Required fields are marked *