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 es 0 y en el bucle desactivar uno de los bits establecidos e invertir 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