# 算法设计：使用XOR和表查找计算数字的奇偶校验

2021年3月17日18:14:43 发表评论 772 次浏览

## 本文概述

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

``````Input : 254
Output : Odd Parity
Explanation : Binary of 254 is 11111110.
There are 7 ones. Thus, parity is odd.

Input : 1742346774
Output : Even``````

## 推荐：请在"实践首先, 在继续解决方案之前。

.

,

1. 如果S1和S2具有相同的奇偶校验, 即它们都具有偶数个位数或奇数个位数, 它们的并集S将具有偶数个位数。
2. 因此, S的奇偶性是S的奇偶性的异或1和S2

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

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

## 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;
}

// 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
?>``````

``Even Parity``