Dado un número entero N. La tarea es escribir un programa para encontrar la paridad del número dado.
Nota : La paridad de un número se usa para definir si el número total de bits establecidos (1 bit en representación binaria) en un número es par o impar. Si el número total de bits establecidos en la representación binaria de un número es par, se dice que el número tiene paridad par; de lo contrario, tendrá paridad impar.
Ejemplos :
Entrada : N = 13
Salida : Paridad impar
Explicación:
La representación binaria de 13 es (1101)Entrada : N = 9 (1001)
Salida : Paridad par
La paridad de un número representado por 32 bits se puede calcular de manera eficiente realizando las siguientes operaciones.
Deje que el número dado sea x, luego realice las siguientes operaciones:
- y = x^(x>>1)
- y = y^(y>>2)
- y = y^(y>>4)
- y = y^(y>>8)
- y = y^(y>>16)
Ahora, el bit más a la derecha en y representará la paridad de x. Si el bit más a la derecha es 1, x tendrá paridad impar y si es 0, x tendrá paridad par.
Entonces, para extraer el último bit de y, realice la operación AND bit a bit de y con 1.
¿Por qué funciona esto?
Considere que queremos encontrar la paridad de n = 150 = 1001 0110 (en binario).
1. Dividamos este número en dos partes y las xor y asignemos a n: n = n ^ (n >> 4) = 1001 ^ 0110 = 1111.
Los bits diferentes dan como resultado un 1 bit en el resultado, mientras que los bits similares dan como resultado un 0. Básicamente, hemos considerado los 8 bits para llegar a este resultado intermedio. Entonces, efectivamente hemos anulado las paridades pares dentro del número.
Ahora repita el paso 1 nuevamente hasta que termine con un solo bit.
n = n ^ (n >> 2) = 11 ^ 11 = 00
n = n ^ (n >> 1) = 0 ^ 0 = 0
Resultado final = n & 1 = 0Otro ejemplo:
n = 1000 0101
n = n ^ (n >> 4) = 1000 ^ 0101 = 1101
n = n ^ (n >> 2) = 11 ^ 01 = 10
n = n ^ (n >> 1) = 1 ^ 0 = 1
Resultado final = n & 1 = 1
if(y&1==1)
odd Parity
else
even Parity
A continuación se muestra la implementación del enfoque anterior:
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
?>
Javascript
<script>
// Javascript Program to find the parity of a given number
// Function to find the parity
function findParity(x) {
let 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) ? document.write("Even Parity<br>") :
document.write("Odd Parity<br>");
(findParity(13) == 0) ? document.write("Even Parity<br>") :
document.write("Odd Parity<br>");
// This code is contributed by _saurabh_jaiswal
</script>
Even Parity Odd Parity
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shubham__Ranjan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA