Kombinierter multiply divide Operation auf 64-Bit-Ganzzahl mit Vorzeichen ohne Überlauf

Question

Ich brauche

zu berechnen

result = (dividend * factor)/divisor 

wo

dividend: full range of int64_t values 
factor: either a full range of uint32_t values or as a special case 2^32 
divisor: positive values of int64_t 
result: is guaranteed to fit in a int32_t 

Ich brauche dies in Klar C/C++ auf einem Mikrocontroller ohne Bibliotheken zu tun. Der Compiler unterstützt die Typen int64_t und uint64_t; wahrscheinlich keine Hardware-Implementierung für Multiplikation oder Division. Derzeit habe ich eine Umgehung für den Uint32_t-Faktor, aber ich brauche eine Lösung für Faktor 2^32.

Answer 1

OP: „Zur Zeit habe ich eine Lösung für den uint32_t Faktor“

Die factor == 2^32 ist eine Ecke Fall und ist alles, was benötigt wird, gelöst werden hier als OPs „Abhilfe“ können Faktoren behandeln [0 ... 2^32-1] .

Wenn die dividend ohne Überlauf verdoppelt werden kann, verwenden Sie einfach factor == 2^31 mit einer doppelten dividend. Wenn die divisor gerade ist, factor == 2^31 mit einem halbierten divisor verwenden. @Weather Vane

Sonst ist die dividend groß. Daran erinnern, dass der Quotient in [-2^31 ... 2^31-1] Bereich ist. Im Allgemeinen wird das Produkt der großen Dividende durch die divisor aus der int32_t Palette, so dass out-of-Range-Kombinationen sind nicht von Belang als "Ergebnis: ist garantiert, um in eine int32_t passen".

Die akzeptablen Randbedingungen treten mit einem Endquotienten nahe dem Rand des int32_t Bereichs auf.

pow(2,63) == 9223372036854775808 
pow(2,62) == 4611686018427387904 
pow(2,32) == 4294967296 
pow(2,31) == 2147483648 

Smallest Dividends Factor  Largest Divisors  Smallest Quotients 
-4611686018427387905 4294967296 -9223372036854775807 2147483648.00+ 
-4611686018427387905 4294967296 9223372036854775807 -2147483648.00+ OK 
4611686018427387904 4294967296 -9223372036854775807 -2147483648.00+ OK 
4611686018427387904 4294967296 9223372036854775807 2147483648.00+ 

Nach dem Test dividend und divisor, die nur darstellbare Antwort in INT32_MIN.

---

Beispielcode:

int32_t muldiv64(int64_t dividend, uint64_t factor, int64_t divisor) { 
    if (factor >= 0x100000000) { 
    assert(factor == 0x100000000); 
    factor /= 2; 
    if (dividend >= INT64_MIN/2 && dividend <= INT64_MAX/2) { 
     dividend *= 2; 
    } else if (divisor %2 == 0) { 
     divisor /= 2; 
    } else { 
     return INT32_MIN; 
    } 
    } 
    return workaround_for_the_uint32_t_factor(dividend, factor, divisor); 
} 

Das ursprüngliche Problem ist, diese Randbedingung zu erfassen und wie sie damit umgehen .. Der workaround_for_the_uint32_t_factor() kann noch nicht codiert worden sind, so war es nicht geschrieben.