¿Cómo puedo con seguridad un promedio de dos enteros sin signo en C ++?

StackOverflow https://stackoverflow.com/questions/3816446

  •  26-09-2019
  •  | 
  •  

Pregunta

Las operaciones aritméticas con enteros solo, me gustaría "segura" promedio de dos enteros sin signo en C ++.

Lo que quiero decir con desbordamientos "de forma segura" es evitar (y cualquier otra cosa que se puede pensar).

Por ejemplo, promediado 200 y 5000 es fácil: 

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

Sin embargo, en el caso de 4294967295 y 5000 a continuación: 

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

Lo mejor que he llegado con es: 

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

¿Hay mejores maneras?

¿Fue útil?

Solución

Su último enfoque parece prometedor. Puede mejorar en ese considerando manualmente los bits más bajos de A y B: 

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

Esto da los resultados correctos en caso de que ambos A y B son impares.

Otros consejos

unsigned int average = low + ((high - low) / 2);

Editar

Aquí hay un artículo relacionado: http : //googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Su método no es correcta si ambos números son, por ejemplo extraña 5 y 7, la media es de 6, pero sus Método # 3 retornos 5.

Prueba esto: 

average = (a>>1) + (b>>1) + (a & b & 1)

con operadores matemáticos solamente: 

average = a/2 + b/2 + (a%2) * (b%2)

Si no te importa un poco x86 línea de montaje (GNU C sintaxis), usted puede tomar ventaja de la sugerencia de supercat al uso rotate-con-carry después de un complemento para poner las altas 32 bits del resultado completo de 33 bits en un registro

Por supuesto, por lo general debe mente utilizando inline-asm, ya que vence algunas optimizaciones ( https://gcc.gnu.org/wiki/DontUseInlineAsm ). Pero aquí vamos de todas formas: 

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

El % modificador para decirle al compilador de los argumentos son conmutativas en realidad no ayuda a hacer un mejor asm en el caso que lo intenté, llamando a la función con y ser una constante o puntero DEREF (operando de memoria). Es probable que el uso de una restricción de coincidencia para una salida operando derrotas que, ya que no se puede utilizar con operandos de lectura y escritura.

Como se puede ver en el Godbolt compilador explorador , Esto compila correctamente, y lo mismo ocurre con una versión en la que cambiamos los operandos a unsigned long, con el mismo asm en línea. clang3.9 hace un lío de ella, sin embargo, y decide utilizar la opción "m" para la restricción "rme", por lo que almacena en la memoria y utiliza una memoria operando.

RCR-por-uno no es demasiado lento, pero aún así es 3 uops en Skylake, con una latencia de 2 tiempos. Es Great en CPUs de AMD, donde RCR tiene una latencia de un solo ciclo. (Fuente: tablas de instrucciones de Agner Fog , consulta la etiqueta wiki para los enlaces de rendimiento x86). Es todavía mejor que la versión de @ sellibitze, pero peor que la versión @ depende del orden de Sheldon. (Ver código en Godbolt)

Pero recuerde que vence en línea-asm optimizaciones como constante de propagación, por lo que cualquier versión pura-C ++ será mejor en ese caso.

Y la respuesta correcta es ... 

(A&B)+((A^B)>>1)

Lo que tienes está muy bien, con el detalle de menor importancia que va a reclamar que el promedio de 3 y 3: 2. supongo que usted no quiere que; Afortunadamente, hay una solución fácil: 

unsigned int average = a/2 + b/2 + (a & b & 1);

Esto se topa la parte posterior media en el caso de que ambas divisiones fueron truncados.

Si el código es para un micro incorporado, y si la velocidad es crítica, lenguaje ensamblador puede ser útil. En muchos microcontroladores, el resultado del complemento, naturalmente, ir a la bandera de acarreo, y existen instrucciones para cambiar de nuevo en un registro. En un brazo, la operación media (fuente y dest en los registros.) Podría ser hecho en dos instrucciones; cualquier lenguaje C equivalente probablemente produciría al menos 5, y probablemente una feria poco más que eso.

Por cierto, en las máquinas con más cortos tamaños de palabra, las diferencias pueden ser aún más importante. En una de 8 bits PIC-18 serie, con un promedio de dos números de 32 bits tomarían doce instrucciones. Haciendo los cambios, complemento, y la corrección, tomaría 5 instrucciones para cada turno, ocho para el complemento, y ocho para la corrección, por lo que 26 (no es una diferencia de 2,5 veces, pero probablemente más importante en términos absolutos).

(((a&b << 1) + (a^b)) >> 1) es también una manera agradable.

Cortesía: http://www.ragestorm.net/blogs/?p=29 

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

Espera avg == 5.0 para esta prueba

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top