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

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

本文概述

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

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

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 ：(幼稚的方法)

我们已经讨论过这种方法

这里

方法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 chunks
   while performing XOR operations.
3. Check for the result in the table for
    the 8-bit number.

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

范例：

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.

下面是实现适用于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
?>

输出如下：