Paridad: 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.
La idea principal de la siguiente solución es: hacer un bucle mientras n no sea 0 y en el bucle desactive uno de los bits establecidos e invierta la paridad.
Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0
a. Invert parity
parity = !parity
b. Unset rightmost set bit
n = n & (n-1)
3. return parity
Example:
Initialize: n = 13 (1101) parity = 0
n = 13 & 12 = 12 (1100) parity = 1
n = 12 & 11 = 8 (1000) parity = 0
n = 8 & 7 = 0 (0000) parity = 1
Programa:
C++
// C++ program to find parity
// of an integer
# include<bits/stdc++.h>
# define bool int
using namespace std;
// Function to get parity of number n. It returns 1
// if n has odd parity, and returns 0 if n has even
// parity
bool getParity(unsigned int n)
{
bool parity = 0;
while (n)
{
parity = !parity;
n = n & (n - 1);
}
return parity;
}
/* Driver program to test getParity() */
int main()
{
unsigned int n = 7;
cout<<"Parity of no "<<n<<" = "<<(getParity(n)? "odd": "even");
getchar();
return 0;
}
C
// C program to find parity
// of an integer
# include <stdio.h>
# define bool int
/* Function to get parity of number n. It returns 1
if n has odd parity, and returns 0 if n has even
parity */
bool getParity(unsigned int n)
{
bool parity = 0;
while (n)
{
parity = !parity;
n = n & (n - 1);
}
return parity;
}
/* Driver program to test getParity() */
int main()
{
unsigned int n = 7;
printf("Parity of no %d = %s", n,
(getParity(n)? "odd": "even"));
getchar();
return 0;
}
Java
// Java program to find parity
// of an integer
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
class GFG
{
/* Function to get parity of number n.
It returns 1 if n has odd parity, and
returns 0 if n has even parity */
static boolean getParity(int n)
{
boolean parity = false;
while(n != 0)
{
parity = !parity;
n = n & (n-1);
}
return parity;
}
/* Driver program to test getParity() */
public static void main (String[] args)
{
int n = 7;
System.out.println("Parity of no " + n + " = " +
(getParity(n)? "odd": "even"));
}
}
/* This code is contributed by Amit khandelwal*/
Python3
# Python3 code to get parity.
# Function to get parity of number n.
# It returns 1 if n has odd parity,
# and returns 0 if n has even parity
def getParity( n ):
parity = 0
while n:
parity = ~parity
n = n & (n - 1)
return parity
# Driver program to test getParity()
n = 7
print ("Parity of no ", n," = ",
( "odd" if getParity(n) else "even"))
# This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to find parity of an integer
using System;
class GFG {
/* Function to get parity of number n.
It returns 1 if n has odd parity, and
returns 0 if n has even parity */
static bool getParity(int n)
{
bool parity = false;
while(n != 0)
{
parity = !parity;
n = n & (n-1);
}
return parity;
}
// Driver code
public static void Main ()
{
int n = 7;
Console.Write("Parity of no " + n
+ " = " + (getParity(n)?
"odd": "even"));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the parity
// of an unsigned integer
// Function to get parity of
// number n. It returns 1
// if n has odd parity, and
// returns 0 if n has even
// parity
function getParity( $n)
{
$parity = 0;
while ($n)
{
$parity = !$parity;
$n = $n & ($n - 1);
}
return $parity;
}
// Driver Code
$n = 7;
echo "Parity of no ",$n ," = " ,
getParity($n)? "odd": "even";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find parity
// of an integer
// Function to get parity of number n.
// It returns 1 if n has odd parity, and
// returns 0 if n has even parity
function getParity(n)
{
var parity = false;
while(n != 0)
{
parity = !parity;
n = n & (n - 1);
}
return parity;
}
// Driver code
var n = 7;
document.write("Parity of no " + n + " = " +
(getParity(n) ? "odd": "even"));
// This code is contributed by Kirti
</script>
Parity of no 7 = odd
La solución anterior se puede optimizar mediante el uso de la tabla de búsqueda. Consulte Bit Twiddle Hacks [primera referencia] para obtener más información.
Complejidad del tiempo: el tiempo que tarda el algoritmo anterior es proporcional al número de bits establecidos. La complejidad del peor de los casos es O (Log n).
Espacio Auxiliar: O(1)
Otro enfoque: (usando la función integrada)
C++
// C++ program to find parity
// of an integer
# include<bits/stdc++.h>
# define bool int
using namespace std;
// Function to get parity of number n. It returns 1
// if n has odd parity, and returns 0 if n has even
// parity
bool getParity(unsigned int n)
{
return __builtin_parity(n);
}
// Driver code
int main()
{
unsigned int n = 7;
cout<<"Parity of no "<<n<<" = "<<(getParity(n)? "odd": "even");
getchar();
return 0;
}
// This code is contributed by Kasina Dheeraj
Parity of no 7 = odd
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Otro enfoque: asignación de números con el bit
Podemos usar un mapa o una array de la cantidad de bits para formar un nibble (un nibble consta de 4 bits, por lo que se requeriría una array de 16 longitudes). Entonces, podemos obtener los nibbles de un número dado.
Este enfoque se puede resumir en los siguientes pasos:
1. Cree la array de 16 longitudes del número de bits para formar un nibble: { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }
2. Cuente recursivamente el conjunto de bits tomando el último nibble (4 bits) de la array usando la fórmula num & 0xf y luego obteniendo cada nibble sucesivo descartando los últimos 4 bits usando el operador >>.
3. Compruebe la paridad: si el número de bits establecidos es par, es decir, numOfSetBits % 2 == 0, entonces el número es de paridad par. De lo contrario, es de paridad impar.
C++
// C++ program to get the parity of the
// binary representation of a number
#include <bits/stdc++.h>
using namespace std;
int nibble_to_bits[16]
= { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
// Function to recursively get the nibble
// of a given number and map them in the array
unsigned int countSetBits(unsigned int num)
{
int nibble = 0;
if (0 == num)
return nibble_to_bits[0];
// Find last nibble
nibble = num & 0xf;
// Use pre-stored values to find count
// in last nibble plus recursively add
// remaining nibbles.
return nibble_to_bits[nibble] + countSetBits(num >> 4);
}
// Function to get the parity of a number
bool getParity(int num) { return countSetBits(num) % 2; }
// Driver code
int main()
{
unsigned int n = 7;
// Function call
cout << "Parity of no " << n << " = "
<< (getParity(n) ? "odd" : "even");
return 0;
}
// This code is contributed by phasing17
Java
// Java program to get the parity of the
// binary representation of a number
import java.util.*;
class GFG{
static int[] nibble_to_bits = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
// Function to recursively get the nibble
// of a given number and map them in the array
static int countSetBits(int num)
{
int nibble = 0;
if (0 == num)
return nibble_to_bits[0];
// Find last nibble
nibble = num & 0xf;
// Use pre-stored values to find count
// in last nibble plus recursively add
// remaining nibbles.
return nibble_to_bits[nibble]
+ countSetBits(num >> 4);
}
// Function to get the parity of a number
static boolean getParity(int num)
{
return countSetBits(num) % 2 == 1;
}
// Driver code
public static void main(String[] args)
{
int n = 7;
// Function call
System.out.print(
"Parity of no " + n + " = "
+ (getParity(n) ? "odd" : "even"));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program to get the parity of the
# binary representation of a number
nibble_to_bits = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
# Function to recursively get the nibble
# of a given number and map them in the array
def countSetBits(num):
nibble = 0
if (0 == num):
return nibble_to_bits[0]
# Find last nibble
nibble = num & 0xf
# Use pre-stored values to find count
# in last nibble plus recursively add
# remaining nibbles.
return nibble_to_bits[nibble] + countSetBits(num >> 4)
# Function to get the parity of a number
def getParity(num):
return countSetBits(num) % 2
# Driver code
n = 7
# Function call
print("Parity of no", n, " = ", ["even", "odd"][getParity(n)])
# This code is contributed by phasing17
C#
// C# program to get the parity of the
// binary representation of a number
using System;
class GFG {
static int[] nibble_to_bits = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
// Function to recursively get the nibble
// of a given number and map them in the array
static int countSetBits(int num)
{
int nibble = 0;
if (0 == num)
return nibble_to_bits[0];
// Find last nibble
nibble = num & 0xf;
// Use pre-stored values to find count
// in last nibble plus recursively add
// remaining nibbles.
return nibble_to_bits[nibble]
+ countSetBits(num >> 4);
}
// Function to get the parity of a number
static bool getParity(int num)
{
return countSetBits(num) % 2 == 1;
}
// Driver code
public static void Main(string[] args)
{
int n = 7;
// Function call
Console.WriteLine(
"Parity of no " + n + " = "
+ (getParity(n) ? "odd" : "even"));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to get the parity of the
// binary representation of a number
let nibble_to_bits
= [ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 ];
// Function to recursively get the nibble
// of a given number and map them in the array
function countSetBits(num)
{
let nibble = 0;
if (0 == num)
return nibble_to_bits[0];
// Find last nibble
nibble = num & 0xf;
// Use pre-stored values to find count
// in last nibble plus recursively add
// remaining nibbles.
return nibble_to_bits[nibble] + countSetBits(num >> 4);
}
// Function to get the parity of a number
function getParity(num) { return countSetBits(num) % 2; }
// Driver code
let n = 7;
// Function call
console.log("Parity of no " + n + " = "+ (getParity(n) ? "odd" : "even"));
// This code is contributed by phasing17
Parity of no 7 = odd
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Usos: la paridad se utiliza en la detección de errores y criptografía.
Calcule la paridad de un número usando XOR y búsqueda de tabla
Referencias:
http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive ; consultado por última vez el 30 de mayo de 2009.
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