Estoy tratando de calcular el paridad de bits de un gran número de uint64. Por paridad de bits me refiero a una función que acepta un uint64 y genera 0 si el número de bits establecidos es par, y 1 en caso contrario.
Actualmente estoy usando la siguiente función (por @Troyseph, que se encuentra aquí):
uint parity64(uint64 n){
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
}
La misma página SO tiene la siguiente rutina de ensamblaje (por @papadp):
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
que aprovecha la máquina bandera de paridad. Pero no puedo hacer que funcione con mi programa C (sé que casi no hay ensamblaje).
Pregunta. ¿Cómo puedo incluir el código anterior (o similar) como ensamblado en línea en mi archivo fuente C, para que el parity64() la función ejecuta eso en su lugar?
(Estoy usando GCC con Ubuntu 14 de 64 bits en un Intel Xeon Haswell)
En caso de que sea de alguna ayuda, el parity64() La función se llama dentro de la siguiente rutina:
uint bindot(uint64* a, uint64* b, uint64 entries){
uint parity = 0;
for(uint i=0; i<entries; ++i)
parity ^= parity64(a[i] & b[i]); // Running sum!
return parity;
}
(Se supone que este es el “producto escalar” de dos vectores sobre el campo Z/2Z, también conocido como GF(2).)
Omitiste el
ULsufijos en el111...–MM
10 de mayo de 2017 a las 4:34
@MM Buena captura, gracias
– étale-cohomología
10 de mayo de 2017 a las 4:35
deberías hacer algo como
uint64 parity = 0;for (...) parity ^= a[i] & b[i];returnparity64(parity);` Esto debería ser más rápido, especialmente si el bucle se vectoriza.– Ross Ridge
10 de mayo de 2017 a las 5:41
@RossRidge Eso corre significativamente más rápido. Voy a convencerme ahora de que las dos versiones son equivalentes.
– étale-cohomología
10 de mayo de 2017 a las 5:48
La paridad es el XOR horizontal de todos los bits. XOR es asociativo, por lo que puede optimizar haciendo XOR “vertical” hasta que tenga un acumulador y luego calculando la paridad de eso.
– Peter Cordes
19 de septiembre de 2017 a las 5:03