La media aritmética de dos enteros sin signo se define como:
mean = (a+b)/2La implementación directa de esto en C/C++ puede desbordarse y producir un resultado incorrecto. Una implementación correcta evitaría esto. Una forma de codificarlo podría ser:
mean = a/2 + b/2 + (a%2 + b%2)/2Pero esto produce bastante código con compiladores típicos. En ensamblador, esto generalmente se puede hacer de manera mucho más eficiente. Por ejemplo, el x86 puede hacer esto de la siguiente manera (pseudocódigo ensamblador, espero que entiendas el punto):
ADD a,b ; addition, leaving the overflow condition in the carry bit RCR a,1 ; rotate right through carry, effectively a division by 2 Después de esas dos instrucciones, el resultado está en a y el resto de la división está en el bit de acarreo. Si se desea un redondeo correcto, una tercera instrucción ADC tendría que agregar el acarreo al resultado.
Tenga en cuenta que se utiliza la instrucción RCR, que gira un registro a través del acarreo. En nuestro caso, es una rotación de una posición, de modo que el acarreo anterior se convierte en el bit más significativo del registro, y el nuevo acarreo contiene el LSB anterior del registro. Parece que MSVC ni siquiera ofrece un intrínseco para esta instrucción.
¿Existe un patrón C/C++ conocido que se pueda esperar que sea reconocido por un compilador optimizador para que produzca un código tan eficiente? O, de manera más general, ¿hay una forma racional de programar en el nivel de fuente C/C++ para que el compilador utilice el bit de acarreo para optimizar el código generado?
EDITAR:
Una conferencia de 1 hora sobre std::midpoint : https://www.youtube.com/watch?v=sBtAGxBh-XI
¡Guau!
Existen tres métodos típicos para calcular el promedio sin desbordamiento, uno de los cuales está limitado a uint32_t (en arquitecturas de 64 bits).
// average "SWAR" / Montgomery uint32_t avg(uint32_t a, uint32_t b) { return (a & b) + ((a ^ b) >> 1); } // in case the relative magnitudes are known uint32_t avg2(uint32_t min, uint32_t max) { return min + (max - min) / 2; } // in case the relative magnitudes are not known uint32_t avg2_constrained(uint32_t a, uint32_t b) { return a + (int32_t)(b - a) / 2; } // average increase width (not applicable to uint64_t) uint32_t avg3(uint32_t a, uint32_t b) { return ((uint64_t)a + b) >> 1; }Las secuencias de ensamblador correspondientes de clang en dos arquitecturas son
avg(unsigned int, unsigned int) mov eax, esi and eax, edi xor esi, edi shr esi add eax, esi avg2(unsigned int, unsigned int) sub esi, edi shr esi lea eax, [rsi + rdi] avg3(unsigned int, unsigned int) mov ecx, edi mov eax, esi add rax, rcx shr raxcontra
avg(unsigned int, unsigned int) and w8, w1, w0 eor w9, w1, w0 add w0, w8, w9, lsr #1 ret avg2(unsigned int, unsigned int) sub w8, w1, w0 add w0, w0, w8, lsr #1 ret avg3(unsigned int, unsigned int): mov w8, w1 add x8, x8, w0, uxtw lsr x0, x8, #1 ret De estas tres versiones, avg2 también funcionaría en ARM64, como la secuencia óptima usando la bandera de acarreo, y también es probable que avg3 funcione también, notando que el mov w8,w1 se usa para borrar los 32 bits superiores , lo que puede ser innecesario dado que el compilador sabe que están borrados por cualquier instrucción anterior que se use para producir el valor.
Se puede hacer una declaración similar de la versión de Intel para avg3 , que en el caso óptimo se compilaría solo con las dos instrucciones significativas:
add rax, rcx shr raxConsulte https://godbolt.org/z/5TMd3zr81 para una comparación en línea.
La versión "SWAR"/Montgomery generalmente solo se justifica cuando se intenta calcular múltiples promedios empaquetados en un solo número entero (grande), en cuyo caso la fórmula completa contiene enmascaramiento con las posiciones de bit de los bits más altos: return (a & b) + (((a ^ b) >> 1) & ~kH; .