算法设计:如何高效地找到数字的奇偶性?

2021年4月1日15:20:59 发表评论 801 次浏览

本文概述

给定整数N。任务是编写程序以查找给定数字的奇偶校验。

注意:数字奇偶校验用于定义数字中设置位(二进制表示形式为1位)的总数是偶数还是奇数。如果一个数字的二进制表示形式中的置位总数为偶数, 则该数字具有偶数奇偶校验, 否则, 它将具有奇数奇偶校验。

例子:

Input : N = 13 
Output : Odd Parity
Binary representation of 13 is (1101)

Input : N = 9 (1001)
Output : Even Parity

通过执行以下操作, 可以有效地计算由32位表示的数字的奇偶校验。

假设给定数字为x, 然后执行以下操作:

  • y = x ^(x >> 1)
  • y = y ^(y >> 2)
  • y = y ^(y >> 4)
  • y = y ^(y >> 8)
  • y = y ^(y >> 16)

现在, y中最右边的位将代表x的奇偶校验。如果最右边的位是1, 则x将具有奇校验, 如果它是0, 则x将具有偶校验。

因此, 为了提取y的最后一位, 请对y与1进行按位与运算。

if(y&1==1)
    odd Parity
else
    even Parity

下面是上述方法的实现:

C ++

// Program to find the parity of a given number
#include <bits/stdc++.h>
  
using namespace std;
  
// Function to find the parity
bool findParity( int x)
{
     int y = x ^ (x >> 1);
     y = y ^ (y >> 2);
     y = y ^ (y >> 4);
     y = y ^ (y >> 8);
     y = y ^ (y >> 16);
  
     // Rightmost bit of y holds the parity value
     // if (y&1) is 1 then parity is odd else even
     if (y & 1)
         return 1;
     return 0;
}
  
// Driver code
int main()
{
     (findParity(9)==0)?cout<< "Even Parity\n" :
                             cout<< "Odd Parity\n" ;
      
     (findParity(13)==0)?cout<< "Even Parity\n" :
                             cout<< "Odd Parity\n" ;
      
     return 0;
}

Java

// Program to find the
// parity of a given number
import java.io.*;
  
class GFG 
{
  
// Function to find the parity
static boolean findParity( int x)
{
     int y = x ^ (x >> 1 );
         y = y ^ (y >> 2 );
         y = y ^ (y >> 4 );
         y = y ^ (y >> 8 );
         y = y ^ (y >> 16 );
  
     // Rightmost bit of y holds
     // the parity value
     // if (y&1) is 1 then parity 
     // is odd else even
     if ((y & 1 ) > 0 )
         return true ;
     return false ;
}
  
// Driver code
public static void main (String[] args) 
{
     if ((findParity( 9 ) == false ))
         System.out.println( "Even Parity" );
     else
         System.out.println( "Odd Parity" );
      
     if (findParity( 13 ) == false )
         System.out.println( "Even Parity" );
     else
         System.out.println( "Odd Parity" );
}
}
  
// This Code is Contributed by chandan_jnu.

Python3

# Program to find the
# parity of a given number
  
# Function to find the parity
def findParity(x):
     y = x ^ (x >> 1 );
     y = y ^ (y >> 2 );
     y = y ^ (y >> 4 );
     y = y ^ (y >> 8 );
     y = y ^ (y >> 16 );
  
     # Rightmost bit of y holds 
     # the parity value if (y&1)
     # is 1 then parity is odd
     # else even
     if (y & 1 ):
         return 1 ;
     return 0 ;
  
# Driver code
if (findParity( 9 ) = = 0 ):
     print ( "Even Parity" );
else :
     print ( "Odd Parity\n" );
  
if (findParity( 13 ) = = 0 ):
     print ( "Even Parity" );
else :
     print ( "Odd Parity" );
      
# This code is contributed by mits

C#

// Program to find the
// parity of a given number
using System;
  
class GFG 
{
  
// Function to find the parity
static bool findParity( int x)
{
     int y = x ^ (x >> 1);
         y = y ^ (y >> 2);
         y = y ^ (y >> 4);
         y = y ^ (y >> 8);
         y = y ^ (y >> 16);
  
     // Rightmost bit of y holds
     // the parity value
     // if (y&1) is 1 then parity 
     // is odd else even
     if ((y & 1) > 0)
         return true ;
     return false ;
}
  
// Driver code
public static void Main () 
{
     if ((findParity(9) == false ))
         Console.WriteLine( "Even Parity" );
     else
         Console.WriteLine( "Odd Parity" );
      
     if (findParity(13) == false )
         Console.WriteLine( "Even Parity" );
     else
         Console.WriteLine( "Odd Parity" );
}
}
  
// This Code is Contributed 
// by chandan_jnu

的PHP

<?php
// Program to find the
// parity of a given number
  
// Function to find the parity
function findParity( $x )
{
     $y = $x ^ ( $x >> 1);
     $y = $y ^ ( $y >> 2);
     $y = $y ^ ( $y >> 4);
     $y = $y ^ ( $y >> 8);
     $y = $y ^ ( $y >> 16);
  
     // Rightmost bit of y holds 
     // the parity value if (y&1)
     // is 1 then parity is odd
     // else even
     if ( $y & 1)
         return 1;
     return 0;
}
  
// Driver code
(findParity(9) == 0) ? 
  print ( "Even Parity\n" ):
  print ( "Odd Parity\n" );
  
(findParity(13) == 0) ? 
print ( "Even Parity\n" ):
print ( "Odd Parity\n" );
      
// This Code is Contributed by mits
?>

输出如下:

Even Parity
Odd Parity

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: