Se stai utilizzando gcc e la versione che hai supporta i numeri a 128 bit (prova ad usare __uint128_t) che eseguire il 128 multiplo ed estrarre i 64 bit superiori è probabile che sia il modo più efficiente per ottenere il risultato.
Se il compilatore non supporta i numeri a 128 bit, la risposta di Yakk è corretta. Tuttavia, potrebbe essere troppo breve per il consumo generale. In particolare, un'implementazione effettiva deve fare attenzione a traboccare interi a 64 bit.
La soluzione semplice e portatile che propone è di interrompere ciascuno di aeb in 2 numeri a 32 bit e quindi moltiplicare quei numeri a 32 bit utilizzando l'operazione di moltiplicazione a 64 bit. Se si scrive:
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;
allora è evidente che:
a = (a_hi << 32) + a_lo;
b = (b_hi << 32) + b_lo;
e:
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
disponibile il calcolo viene eseguito utilizzando 128 bit (o superiore) aritmetica.
Ma questo problema richiede che eseguiamo tutti i calcoli utilizzando l'aritmetica a 64 bit, quindi dobbiamo preoccuparci dell'overflow.
Poiché a_hi, a_lo, b_hi e b_lo sono tutti numeri a 32 bit senza segno, il loro prodotto si adatta a un numero a 64 bit senza segno di overflow. Tuttavia, i risultati intermedi del calcolo di cui sopra non lo faranno.
Il codice seguente attuerà mulhi (a, b) quando le mathemetics devono essere eseguite 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;
Come Yakk rileva, se non mente essere fuori da +1 a i 64 bit superiori, è possibile omettere il calcolo del bit di carry.
Riferimento: http://blogs.msdn.com/b/oldnewthing/archive/2014/12/08/10578956.aspx –
GCC ha 'uint128_t' per questo scopo. Tuttavia, Visual Studio non ha questa opzione. –
@MooingDuck Sembra che uint128_t non esista sotto il mio ambiente (sto usando Xcode sotto osx). Inoltre, questo calcolerà esplicitamente sia la parte superiore che quella inferiore di quella moltiplicazione, che vorrei evitare. –