¿Cómo puedo comprobar si un valor tiene paridad de bits par o impar?

6 minutos de lectura

avatar de usuario
Manuel

Un valor tiene incluso la paridad si tiene un número par de bits ‘1’. Un valor tiene una paridad impar si tiene un número impar de bits ‘1’. Por ejemplo, 0110 tiene paridad par y 1110 tiene paridad impar.

tengo que volver 1 si x tiene incluso paridad.

int has_even_parity(unsigned int x) {
    return
}

  • Bienvenido a SO. Lea Cómo preguntar y el centro de ayuda sobre cómo hacer una pregunta. Ve a leer sobre el cambio de bits en C.

    – Antiguo programador

    7 de febrero de 2014 a las 2:11


  • @OldProgrammer ¿Se requiere eso? No me queda claro que se deba esperar que el OP sepa buscar eso. Es una pregunta justa y clara.

    – TipoIA

    7 de febrero de 2014 a las 2:16

  • Posible duplicado del código de paridad de bits para un número impar de bits

    – Troyseph

    27 de octubre de 2015 a las 9:58

  • Consulte aquí: stackoverflow.com/questions/21589674/even-parity-of-a-unsigned-int.

    – Troyseph

    27/10/2015 a las 10:03


  • El caso más general (y más lento) es Cuente el número de bits establecidos en un entero de 32 bits

    -Peter Mortensen

    hace 13 horas


avatar de usuario
TipoIA

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

Suponiendo que sabe que los ints son de 32 bits.


Veamos cómo funciona esto. Para simplificar, usemos un número entero de 8 bits, para el cual podemos omitir los dos primeros shift/XOR. Vamos a etiquetar los bits a mediante h. Si miramos nuestro número vemos:

( a b C d mi F gramo h )


La primera operación es x ^= x >> 4 (recuerde que nos estamos saltando las dos primeras operaciones ya que en este ejemplo solo estamos tratando con un número entero de 8 bits). Escribamos los nuevos valores de cada bit combinando las letras que tienen XOR juntas (por ejemplo, abdominales significa que el bit tiene el valor a xor b).

( a b C d mi F gramo h ) x o ( 0 0 0 0 a b C d )

El resultado son los siguientes bits:

( a b C d ae novio c.g. dh )


La siguiente operación es x ^= x >> 2:

( a b C d ae novio c.g. dh ) x o ( 0 0 a b C d ae novio )

El resultado son los siguientes bits:

( a b C.A bd as bdf aceg bdfh )

Observe cómo estamos comenzando a acumular todos los bits en el lado derecho.


La siguiente operación es x ^= x >> 1:

( a b C.A bd as bdf aceg bdfh ) x o ( 0 a b C.A bd as bdf aceg )

El resultado son los siguientes bits:

( a abdominales a B C a B C D a B C D e a B C D e F abcdefg abcdefgh )


Hemos acumulado todos los bits en la palabra original, combinados con XOR, en el bit menos significativo. Entonces, este bit ahora es cero si y solo si hubiera un número par de bits 1 en la palabra de entrada (paridad par). El mismo proceso funciona con enteros de 32 bits (pero requiere esos dos turnos adicionales que omitimos en esta demostración).

La última línea de código simplemente elimina todo menos el bit menos significativo (& 1) y luego lo voltea (~x). El resultado, entonces, es 1 si la paridad de la palabra de entrada fue par, o cero en caso contrario.

  • La última línea de código voltea bits y luego elimina los otros bits (su explicación tiene esos dos al revés)

    –MM

    17 de agosto de 2017 a las 4:13

avatar de usuario
Antti Haapala — Слава Україні

CCG tiene funciones integradas para esto:

Función incorporada: int __builtin_parity (unsigned int x)

Devuelve la paridad de xes decir, el número de bits de 1 en x módulo 2.

y funciones similares para unsigned long y unsigned long long.

Es decir, esta función se comporta como has_odd_parity. invertir el valor de has_even_parity.

Estas deberían ser la alternativa más rápida en GCC. Por supuesto, su uso no es portátil como tal, pero puede usarlo en su implementación, protegido por una macro, por ejemplo.

  • En lugar de reinventar la rueda en diferentes formas y tamaños, creo que este es el mejor enfoque.

    – faruk13

    5 de julio de 2019 a las 17:05

La siguiente respuesta fue sacada desvergonzadamente directamente de Bit Twiddling Hacks Por Sean Eron Anderson, [email protected]

Calcular la paridad de palabra con una multiplicación

El siguiente método calcula la paridad del valor de 32 bits en solo 8 operaciones > utilizando una multiplicación.

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

También para 64 bits, 8 operaciones siguen siendo suficientes.

unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;

A Andrew Shapira se le ocurrió esto y me lo envió el 2 de septiembre de 2007.

avatar de usuario
γηράσκω δ’ αεί πολλά διδασκόμε

Probar:

int has_even_parity(unsigned int x){
    unsigned int count = 0, i, b = 1;

    for(i = 0; i < 32; i++){
        if( x & (b << i) ){count++;}
    }

    if( (count % 2) ){return 0;}

    return 1;
}

avatar de usuario
rishava ambasta

Para generalizar la respuesta de TypeIA para cualquier arquitectura:

int has_even_parity(unsigned int x) 
{
    unsigned char shift = 1;
    while (shift < (sizeof(x)*8))
    {
        x ^= (x >> shift);
        shift <<= 1;
    }
    return !(x & 0x1);
}

  • Esto no es para ninguna arquitectura.

    – Antti Haapala — Слава Україні

    31 de diciembre de 2017 a las 9:18

avatar de usuario
madhu sudhan

La idea principal es esta. Desactive el bit ‘1’ más a la derecha usando x & ( x - 1 ). Digamos x = 13(1101) y la operación de x & ( x - 1 ) es 1101 & 1100 que es 1100, observe que el bit establecido más a la derecha se convierte en 0.

Ahora x es 1100. La operación de x & ( x - 1 ) es decir 1100 & 1011 es 1000. Observe que el original x es 1101 y después de dos operaciones de x & (x - 1) la x es 1000, es decir, dos bits establecidos se eliminan después de dos operaciones. si despues odd número de operaciones, el x se convierte en cero, entonces es una paridad impar, de lo contrario es una paridad par.

  • Esto no es para ninguna arquitectura.

    – Antti Haapala — Слава Україні

    31 de diciembre de 2017 a las 9:18

Aquí está un una línea #define eso hace el truco para un char:

#define PARITY(x) ((~(x ^= (x ^= (x ^= x >> 4) >> 2) >> 1)) & 1) /* even parity */

int main()
{
    char x=3;
    printf("parity = %d\n", PARITY(x));
}

Es portátil como diablos y se modifica fácilmente para trabajar con palabras más grandes (16, 32 bits). Es importante notar también, usando un #define acelera el código, cada llamada de función requiere tiempo para empujar la pila y asignar memoria. El tamaño del código no sufre, especialmente si se implementa solo unas pocas veces en su código: la llamada a la función puede ocupar tanto código objeto como los XOR.

Es cierto que se pueden obtener las mismas eficiencias utilizando el en línea versión funcional de esto, inline char parity(char x) {return PARITY(x);} (CCG) o __inline char parity(char x) {return PARITY(x);} (MSVC). Suponiendo que mantenga la definición de una línea.

  • Esto no es estrictamente correcto, debe usarse para caracteres sin firmarNo firmado

    – Antti Haapala — Слава Україні

    6 de julio de 2019 a las 4:07

  • Oppsies, tienes razón, gracias. Sin embargo, no modificaré la publicación, será trivial para aquellos que la usan arreglarla. (O no).

    – Danny Holstein

    7 julio 2019 a las 21:38


¿Ha sido útil esta solución?