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.

1 --> parity of the set is odd 0 --> parity of the set is even

**Examples:**

Input : 254 Output : Odd ParityExplanation :Binary of 254 is 11111110. There are 7 ones. Thus, parity is odd. Input : 1742346774 Output : Even

**Method 1 : (Naive approach)**

We have already discussed this method here.

**Method 2 : (Efficient)**

Pr-requisites : Table look up, X-OR magic

If we break a number S into two parts S_{1} and S_{2} such **S = S _{1}S_{2}**. If we know parity of S

_{1}and S

_{2}, we can compute parity of S using below facts :

- If S
_{1}and S_{2}have the same parity, i.e. they both have an even number of bits or an odd number of bits, their union S will have an even number of bits. - Therefore parity of S is XOR of parities of S
_{1}and S_{2}

The idea is to create a look up table to store parities of all 8 bit numbers. Then compute parity of whole number by dividing it into 8 bit numbers and using above facts.

**Steps:**

1. Create a look-up table for 8-bit numbers ( 0 to 255 ) Parity of 0 is 0. Parity of 1 is 1. . . . Parity of 255 is 0. 2. Break the number into 8-bit chunks while performing XOR operations. 3. Check for the result in the table for the 8-bit number.

Since a 32 bit or 64 bit number contains constant number of bytes, the above steps take O(1) time.

**Example :**

1. Take 32-bit number :17423467742. Calculate Binary of the number :011001111101101000011010000101103. Split the 32-bit binary representation into 16-bit chunks :0110011111011010 | 00011010000101104. Compute X-OR : 0110011111011010 ^ 0001101000010110 ___________________ = 0111110111001100 5. Split the 16-bit binary representation into 8-bit chunks : 01111101 | 11001100 6. Again, Compute X-OR : 01111101 ^ 11001100 ___________________ = 1011000110110001 is 177 in decimal. Check for its parity in look-up table :Even number of 1 = Even parity.Thus, Parity of 1742346774 is even.

Below is the implementation that **works for both 32 bit and 64 bit** numbers.

## C++

`// CPP program to illustrate Compute the parity of a ` `// number using XOR ` `#include <bits/stdc++.h> ` ` ` `// Generating the look-up table while pre-processing ` `#define P2(n) n, n ^ 1, n ^ 1, n ` `#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n) ` `#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n) ` `#define LOOK_UP P6(0), P6(1), P6(1), P6(0) ` ` ` `// LOOK_UP is the macro expansion to generate the table ` `unsigned ` `int` `table[256] = { LOOK_UP }; ` ` ` `// Function to find the parity ` `int` `Parity(` `int` `num) ` `{ ` ` ` `// Number is considered to be of 32 bits ` ` ` `int` `max = 16; ` ` ` ` ` `// Dividing the number into 8-bit ` ` ` `// chunks while performing X-OR ` ` ` `while` `(max >= 8) { ` ` ` `num = num ^ (num >> max); ` ` ` `max = max / 2; ` ` ` `} ` ` ` ` ` `// Masking the number with 0xff (11111111) ` ` ` `// to produce valid 8-bit result ` ` ` `return` `table[num & 0xff]; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `unsigned ` `int` `num = 1742346774; ` ` ` ` ` `// Result is 1 for odd parity, 0 for even parity ` ` ` `bool` `result = Parity(num); ` ` ` ` ` `// Printing the desired result ` ` ` `result ? std::cout << ` `"Odd Parity"` `: ` ` ` `std::cout << ` `"Even Parity"` `; ` ` ` ` ` `return` `0; ` `} ` |

## Python3

# Python3 program to illustrate Compute the

# parity of a number using XOR

# Generating the look-up table while

# pre-processing

def P2(n, table):

table.extend([n, n ^ 1, n ^ 1, n])

def P4(n, table):

return (P2(n, table), P2(n ^ 1, table),

P2(n ^ 1, table), P2(n, table))

def P6(n, table):

return (P4(n, table), P4(n ^ 1, table),

P4(n ^ 1, table), P4(n, table))

def LOOK_UP(table):

return (P6(0, table), P6(1, table),

P6(1, table), P6(0, table))

# LOOK_UP is the macro expansion to

# generate the table

table = [0] * 256

LOOK_UP(table)

# Function to find the parity

def Parity(num) :

# Number is considered to be

# of 32 bits

max = 16

# Dividing the number o 8-bit

# chunks while performing X-OR

while (max >= 8):

num = num ^ (num >> max)

max = max // 2

# Masking the number with 0xff (11111111)

# to produce valid 8-bit result

return table[num & 0xff]

# Driver code

if __name__ ==”__main__”:

num = 1742346774

# Result is 1 for odd parity,

# 0 for even parity

result = Parity(num)

print(“Odd Parity”) if result else print(“Even Parity”)

# This code is contributed by

# Shubham Singh(SHUBHAMSINGH10)

## PHP

`<?php ` `// PHP program to illustrate ` `// Compute the parity of a ` `// number using XOR ` ` ` `/* Generating the look-up ` `table while pre-processing ` `#define P2(n) n, n ^ 1, n ^ 1, n ` `#define P4(n) P2(n), P2(n ^ 1), ` ` ` `P2(n ^ 1), P2(n) ` `#define P6(n) P4(n), P4(n ^ 1), ` ` ` `P4(n ^ 1), P4(n) ` `#define LOOK_UP P6(0), P6(1), ` ` ` `P6(1), P6(0) ` ` ` `LOOK_UP is the macro expansion ` `to generate the table ` `$table = array(LOOK_UP ); ` `*/` ` ` `// Function to find ` `// the parity ` `function` `Parity(` `$num` `) ` `{ ` ` ` `global` `$table` `; ` ` ` ` ` `// Number is considered ` ` ` `// to be of 32 bits ` ` ` `$max` `= 16; ` ` ` ` ` `// Dividing the number ` ` ` `// into 8-bit chunks ` ` ` `// while performing X-OR ` ` ` `while` `(` `$max` `>= 8) ` ` ` `{ ` ` ` `$num` `= ` `$num` `^ (` `$num` `>> ` `$max` `); ` ` ` `$max` `= (int)` `$max` `/ 2; ` ` ` `} ` ` ` ` ` `// Masking the number with ` ` ` `// 0xff (11111111) to produce ` ` ` `// valid 8-bit result ` ` ` `return` `$table` `[` `$num` `& 0xff]; ` `} ` ` ` `// Driver code ` `$num` `= 1742346774; ` ` ` `// Result is 1 for odd ` `// parity, 0 for even parity ` `$result` `= Parity(` `$num` `); ` ` ` `// Printing the desired result ` `if` `(` `$result` `== true) ` ` ` `echo` `"Odd Parity"` `; ` ` ` `else` ` ` `echo` `"Even Parity"` `; ` ` ` `// This code is contributed by ajit ` `?> ` |

**Output:**

Even Parity

**Time Complexity :** O(1). Note that a 32 bit or 64 bit number has fixed number of bytes (4 in case of 32 bits and 8 in case of 64 bits).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments