c++ - que - Obtener la parte alta de la multiplicación de enteros de 64 bits

tipos de datos enteros

Question

Esta pregunta ya tiene una respuesta aquí:

• Cálculo eficiente de los bits de orden superior de una multiplicación 3 respuestas

En C ++, di que:

uint64_t i;
uint64_t j;

entonces i * j dará un uint64_t que tiene como valor la parte inferior de la multiplicación entre i y j , es decir, (i * j) mod 2^64 . Ahora, ¿y si quisiera la parte más alta de la multiplicación? Sé que existe una instrucción de ensamblaje para algo así cuando se usan enteros de 32 bits, pero no estoy familiarizado en absoluto con el ensamblaje, así que esperaba ayuda.

¿Cuál es la forma más eficiente de hacer algo como esto?

uint64_t k = mulhi(i, j);

Answer 1

La multiplicación larga debería ser un buen rendimiento.

Dividir a*b en (hia+loa)*(hib+lob) . Esto proporciona 4 multiplicaciones de 32 bits más algunos cambios. Hazlos en 64 bits, y haz los acarreos manualmente, y obtendrás la porción alta.

Tenga en cuenta que una aproximación de la porción alta se puede hacer con menos multiplicaciones: precisa dentro de 2 ^ 33 o así con 1 multiplicación, y dentro de 1 con 3 multiplicaciones.

No creo que haya una alternativa portátil.

Answer 2

Si está utilizando gcc y la versión que tiene es compatible con números de 128 bits (intente usar __uint128_t) que realizar la multiplicación 128 y extraer los 64 bits superiores es probable que sea la forma más eficiente de obtener el resultado.

Si su compilador no admite números de 128 bits, entonces la respuesta de Yakk es correcta. Sin embargo, puede ser demasiado breve para el consumo general. En particular, una implementación real tiene que tener cuidado de desbordar integars de 64 bits.

La solución simple y portátil que propone es dividir cada uno de ay b en 2 números de 32 bits y luego multiplicar esos números de 32 bits utilizando la operación de multiplicar de 64 bits. Si escribimos:

uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;

entonces es obvio que:

a = (a_hi << 32) + a_lo;
b = (b_hi << 32) + b_lo;

y:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)
      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

siempre que el cálculo se realice usando una aritmética de 128 bit (o mayor).

Pero este problema requiere que realicemos todos los cálculos usando una aritmética de 64 bits, por lo que debemos preocuparnos por el desbordamiento.

Como a_hi, a_lo, b_hi y b_lo son todos números de 32 bits sin firmar, su producto encajará en un número sin signo de 64 bits sin desbordamiento. Sin embargo, los resultados intermedios del cálculo anterior no lo harán.

El siguiente código implementará mulhi (a, b) cuando los mathemetics se deben realizar modulo 2 ^ 64:

uint64_t    a_lo = (uint32_t)a;
uint64_t    a_hi = a >> 32;
uint64_t    b_lo = (uint32_t)b;
uint64_t    b_hi = b >> 32;

uint64_t    a_x_b_hi =  a_hi * b_hi;
uint64_t    a_x_b_mid = a_hi * b_lo;
uint64_t    b_x_a_mid = b_hi * a_lo;
uint64_t    a_x_b_lo =  a_lo * b_lo;

uint64_t    carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
                         (uint64_t)(uint32_t)b_x_a_mid +
                         (a_x_b_lo >> 32) ) >> 32;

uint64_t    multhi = a_x_b_hi +
                     (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                     carry_bit;

return multhi;

Como señala Yakk, si no le molesta estar fuera por +1 en los 64 bits superiores, puede omitir el cálculo del bit de acarreo.