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 an odd number of 1-bits and is “even parity” if it contains an even number of 1-bits.
The 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<bits/stdc++.h># define bool intusing 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 "<<n<<" = "<<(getParity(n)? "odd": "even"); getchar(); return 0;} |
C
// C program to find parity// of an integer# include <stdio.h># 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 integerimport 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 = 7; 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 paritydef getParity( n ): parity = 0 while n: parity = ~parity n = n & (n - 1) return parity# Driver program to test getParity()n = 7print ("Parity of no ", n," = ", ( "odd" if getParity(n) else "even"))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to find parity of an integerusing 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
<?php// PHP program to find the parity// of an unsigned integer// Function to get parity of // number n. It returns 1// if n has odd parity, and// returns 0 if n has even// parityfunction getParity( $n){ $parity = 0; while ($n) { $parity = !$parity; $n = $n & ($n - 1); } return $parity;} // Driver Code $n = 7; echo "Parity of no ",$n ," = " , getParity($n)? "odd": "even"; // This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to find parity// of an integer// Function to get parity of number n.// It returns 1 if n has odd parity, and// returns 0 if n has even parity function getParity(n){ var parity = false; while(n != 0) { parity = !parity; n = n & (n - 1); } return parity;} // Driver codevar n = 7;document.write("Parity of no " + n + " = " + (getParity(n) ? "odd": "even")); // This code is contributed by Kirti</script> |
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).
Auxiliary Space: O(1)
Another approach: (Using built-in-function)
C++
// C++ program to find parity// of an integer# include<bits/stdc++.h># define bool intusing 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){ return __builtin_parity(n);}// Driver codeint main(){ unsigned int n = 7; cout<<"Parity of no "<<n<<" = "<<(getParity(n)? "odd": "even"); getchar(); return 0;}// This code is contributed by Kasina Dheeraj |
Java
// Java program to implement approachimport java.util.*;class Main { // Function to get parity of number n. It returns 1 // if n has odd parity, and returns 0 if n has even // parity public static boolean getParity(int n) { return Integer.bitCount(n) % 2 == 1; } // Driver code public static void main(String[] args) { int n = 7; System.out.println("Parity of no " + n + " = " + (getParity(n) ? "odd" : "even")); }}// This code is contributed by phasing17 |
Python3
# Python program to find parity# of an integer# Function to get parity of number n. It returns 1# if n has odd parity, and returns 0 if n has even# paritydef getParity(n): return (bin(n).count("1"))%2# Driver coden=7print("Parity of no {0} = ".format(n),end="")print("odd" if getParity(n) else "even")# This code is contributed by Pushpesh Raj |
C#
// C# code to implement the approachusing System;using System.Linq;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 public static bool GetParity(int n) { return Convert.ToInt32(Convert.ToString(n, 2).Count(x => x == '1')) % 2 == 1; } // Driver code public static void Main() { int n = 7; Console.WriteLine("Parity of no " + n + " = " + (GetParity(n) ? "odd" : "even")); }}// This code is contributed by phasing17 |
Javascript
// JS program to implement the above approach// Function to get parity of number n. It returns 1// if n has odd parity, and returns 0 if n has even parityconst getParity = (n) => { return (n.toString(2).split("1").length - 1) % 2;};// Driver codeconst n = 7;console.log(`Parity of no ${n} =`, getParity(n) ? "odd" : "even");// This code is implemented by Phasing17 |
Output
Parity of no 7 = odd
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach: Mapping numbers with the bit
We can use a map or an array of the number of bits to form a nibble (a nibble consists of 4 bits, so a 16 – length array would be required). Then, we can get the nibbles of a given number.
This approach can be summarized into the following steps:
1. Build the 16 length array of the number of bits to form a nibble – { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }
2. Recursively count the set of the bits by taking the last nibble (4 bits) from the array using the formula num & 0xf and then getting each successive nibble by discarding the last 4 bits using >> operator.
3. Check the parity: if the number of set bits is even, ie numOfSetBits % 2 == 0, then the number is of even parity. Else, it is of odd parity.
C++
// C++ program to get the parity of the// binary representation of a number#include <bits/stdc++.h>using namespace std;int nibble_to_bits[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };// Function to recursively get the nibble// of a given number and map them in the arrayunsigned int countSetBits(unsigned int num){ int nibble = 0; if (0 == num) return nibble_to_bits[0]; // Find last nibble nibble = num & 0xf; // Use pre-stored values to find count // in last nibble plus recursively add // remaining nibbles. return nibble_to_bits[nibble] + countSetBits(num >> 4);}// Function to get the parity of a numberbool getParity(int num) { return countSetBits(num) % 2; }// Driver codeint main(){ unsigned int n = 7; // Function call cout << "Parity of no " << n << " = " << (getParity(n) ? "odd" : "even"); return 0;}// This code is contributed by phasing17 |
Java
// Java program to get the parity of the// binary representation of a numberimport java.util.*;class GFG{ static int[] nibble_to_bits = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; // Function to recursively get the nibble // of a given number and map them in the array static int countSetBits(int num) { int nibble = 0; if (0 == num) return nibble_to_bits[0]; // Find last nibble nibble = num & 0xf; // Use pre-stored values to find count // in last nibble plus recursively add // remaining nibbles. return nibble_to_bits[nibble] + countSetBits(num >> 4); } // Function to get the parity of a number static boolean getParity(int num) { return countSetBits(num) % 2 == 1; }// Driver codepublic static void main(String[] args){ int n = 7; // Function call System.out.print( "Parity of no " + n + " = " + (getParity(n) ? "odd" : "even"));}}// This code is contributed by sanjoy_62. |
Python3
# Python3 program to get the parity of the# binary representation of a numbernibble_to_bits = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]# Function to recursively get the nibble# of a given number and map them in the arraydef countSetBits(num): nibble = 0 if (0 == num): return nibble_to_bits[0] # Find last nibble nibble = num & 0xf # Use pre-stored values to find count # in last nibble plus recursively add # remaining nibbles. return nibble_to_bits[nibble] + countSetBits(num >> 4)# Function to get the parity of a numberdef getParity(num): return countSetBits(num) % 2# Driver coden = 7# Function callprint("Parity of no", n, " = ", ["even", "odd"][getParity(n)])# This code is contributed by phasing17 |
C#
// C# program to get the parity of the// binary representation of a numberusing System;class GFG { static int[] nibble_to_bits = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; // Function to recursively get the nibble // of a given number and map them in the array static int countSetBits(int num) { int nibble = 0; if (0 == num) return nibble_to_bits[0]; // Find last nibble nibble = num & 0xf; // Use pre-stored values to find count // in last nibble plus recursively add // remaining nibbles. return nibble_to_bits[nibble] + countSetBits(num >> 4); } // Function to get the parity of a number static bool getParity(int num) { return countSetBits(num) % 2 == 1; } // Driver code public static void Main(string[] args) { int n = 7; // Function call Console.WriteLine( "Parity of no " + n + " = " + (getParity(n) ? "odd" : "even")); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to get the parity of the// binary representation of a numberlet nibble_to_bits = [ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 ];// Function to recursively get the nibble// of a given number and map them in the arrayfunction countSetBits(num){ let nibble = 0; if (0 == num) return nibble_to_bits[0]; // Find last nibble nibble = num & 0xf; // Use pre-stored values to find count // in last nibble plus recursively add // remaining nibbles. return nibble_to_bits[nibble] + countSetBits(num >> 4);}// Function to get the parity of a numberfunction getParity(num) { return countSetBits(num) % 2; }// Driver codelet n = 7;// Function callconsole.log("Parity of no " + n + " = "+ (getParity(n) ? "odd" : "even"));// This code is contributed by phasing17 |
Output
Parity of no 7 = odd
Time Complexity: O(1)
Auxiliary Space: O(1)
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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
