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

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 Parity
Explanation : 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 S1 and S2 such S = S1S2. If we know parity of S1 and S2, we can compute parity of S using below facts :

1. If S1 and S2 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.
2. Therefore parity of S is XOR of parities of S1 and S2

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 : 1742346774

2. Calculate Binary of the number :
01100111110110100001101000010110

3. Split the 32-bit binary representation into
16-bit chunks :
0110011111011010 | 0001101000010110

4. 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
___________________
= 10110001
10110001 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 ` ` `  `// 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 = { 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 =  * 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

 `= 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).