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// paritybool 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 parityfunction 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// paritybool 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.