La paridad de un número se refiere a si contiene un número par o impar de 1 bit. El número tiene «paridad impar», si contiene un número impar de 1 bits y es «paridad par» si contiene un número par de 1 bits.
1 --> parity of the set is odd 0 --> parity of the set is even
Ejemplos:
Input : 254 Output : Odd Parity Explanation : Binary of 254 is 11111110. There are 7 ones. Thus, parity is odd. Input : 1742346774 Output : Even
Método 1: (Enfoque ingenuo) Ya hemos discutido este método aquí . Método 2: (Eficiente) Pre-requisitos: Tabla de búsqueda , magia X-OR Si descomponemos un número S en dos partes S 1 y S 2 tal S = S 1 S 2 . Si conocemos la paridad de S 1 y S 2 , podemos calcular la paridad de S usando los siguientes hechos:
- Si S 1 y S 2 tienen la misma paridad, es decir, ambos tienen un número par de bits o un número impar de bits, su unión S tendrá un número par de bits.
- Por lo tanto, la paridad de S es XOR de las paridades de S 1 y S 2
La idea es crear una tabla de consulta para almacenar paridades de todos los números de 8 bits. Luego calcule la paridad del número entero dividiéndolo en números de 8 bits y usando los hechos anteriores. Pasos:
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.
Dado que un número de 32 o 64 bits contiene un número constante de bytes, los pasos anteriores requieren un tiempo O(1). Ejemplo :
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.
A continuación se muestra la implementación que funciona tanto para números de 32 bits como de 64 bits .
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;
}
Java
// Java program to illustrate Compute the
// parity of a number using XOR
import java.util.ArrayList;
class GFG {
// LOOK_UP is the macro expansion to
// generate the table
static ArrayList<Integer> table = new ArrayList<Integer>();
// Generating the look-up table while
// pre-processing
static void P2(int n)
{
table.add(n);
table.add(n ^ 1);
table.add(n ^ 1);
table.add(n);
}
static void P4(int n)
{
P2(n);
P2(n ^ 1);
P2(n ^ 1);
P2(n);
}
static void P6(int n)
{
P4(n);
P4(n ^ 1);
P4(n ^ 1);
P4(n) ;
}
static void LOOK_UP()
{
P6(0);
P6(1);
P6(1);
P6(0);
}
// Function to find the parity
static int Parity(int num)
{
// Number is considered to be
// of 32 bits
int 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.get(num & 0xff);
}
public static void main(String[] args) {
// Driver code
int num = 1742346774;
LOOK_UP();
//Function call
int result = Parity(num);
// Result is 1 for odd parity,
// 0 for even parity
if (result != 0)
System.out.println("Odd Parity");
else
System.out.println("Even Parity");
}
}
//This code is contributed by phasing17
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)
C#
// C# program to illustrate Compute the
// parity of a number using XOR
using System;
using System.Collections.Generic;
class GFG {
// LOOK_UP is the macro expansion to
// generate the table
static List<int> table = new List<int>();
// Generating the look-up table while
// pre-processing
static void P2(int n)
{
table.Add(n);
table.Add(n ^ 1);
table.Add(n ^ 1);
table.Add(n);
}
static void P4(int n)
{
P2(n);
P2(n ^ 1);
P2(n ^ 1);
P2(n);
}
static void P6(int n)
{
P4(n);
P4(n ^ 1);
P4(n ^ 1);
P4(n);
}
static void LOOK_UP()
{
P6(0);
P6(1);
P6(1);
P6(0);
}
// Function to find the parity
static int Parity(int num)
{
// Number is considered to be
// of 32 bits
int 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];
}
public static void Main(string[] args)
{
// Driver code
int num = 1742346774;
LOOK_UP();
// Function call
int result = Parity(num);
// Result is 1 for odd parity,
// 0 for even parity
if (result != 0)
Console.WriteLine("Odd Parity");
else
Console.WriteLine("Even Parity");
}
}
// This code is contributed by phasing17
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
?>
Javascript
//JavaScript program to illustrate Compute the
// parity of a number using XOR
// Generating the look-up table while
// pre-processing
function P2(n, table)
{
table.push(n, n ^ 1, n ^ 1, n);
}
function P4(n, table)
{
return (P2(n, table), P2(n ^ 1, table),
P2(n ^ 1, table), P2(n, table));
}
function P6(n, table)
{
return (P4(n, table), P4(n ^ 1, table),
P4(n ^ 1, table), P4(n, table)) ;
}
function 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
var table = new Array(256).fill(0);
LOOK_UP(table);
// Function to find the parity
function Parity(num)
{
// Number is considered to be
// of 32 bits
var max = 16;
// Dividing the number o 8-bit
// chunks while performing X-OR
while (max >= 8)
{
num = num ^ (num >> max);
max = Math.floor(max / 2);
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff] ;
}
// Driver code
var num = 1742346774;
//Function call
var result = Parity(num);
// Result is 1 for odd parity,
// 0 for even parity
console.log(result ? "Odd Parity" : "Even Parity");
// This code is contributed by phasing17
Producción:
Even Parity
Complejidad temporal: O(1). Tenga en cuenta que un número de 32 o 64 bits tiene un número fijo de bytes (4 en el caso de 32 bits y 8 en el caso de 64 bits). Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA