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

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Python3
的PHP

数字奇偶校验是指它是否包含奇数或偶数个1位。如果该数字包含奇数个1位, 则具有"奇校验", 如果包含偶数个1位, 则具有"偶校验"。

1 --> parity of the set is odd0 --> parity of the set is even

例子：

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

推荐：请在"实践首先, 在继续解决方案之前。方法1 ：(幼稚的方法)
我们已经讨论过这种方法
这里
.
方法2：(有效)
前提条件：
查表
,
异或魔术
如果我们将数字S分为两部分1和S2这样S = S1小号2。如果我们知道S的奇偶性1和S2, 我们可以使用以下事实来计算S的奇偶校验：

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

这个想法是创建一个查找表来存储所有8位数字的奇偶校验。然后通过将整数除以8位数字并使用上述事实来计算整数的奇偶校验。
步骤如下：

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 chunkswhile performing XOR operations.3. Check for the result in the table forthe 8-bit number.

由于32位或64位数字包含恒定数量的字节, 因此上述步骤需要O(1)时间。
范例：

1. Take 32-bit number : 17423467742. Calculate Binary of the number : 011001111101101000011010000101103. Split the 32-bit binary representation into 16-bit chunks :0110011111011010 | 0001101000010110 4. Compute X-OR :0110011111011010^ 0001101000010110___________________= 01111101110011005. Split the 16-bit binary representation into 8-bit chunks : 01111101 | 110011006. 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.

下面是实现适用于32位和64位数字。
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 ?>

输出如下：