Teilen Sie in C ++ Ganzzahlen durch Boden-, Decken- und Außenrundungsmodi
Kürzlich habe ich diese Frage gesehen, in der gefragt wird, wie Sie ganze Zahlen durch Deckenrundung (in Richtung positive Unendlichkeit) teilen können . Leider funktionieren die Antworten entweder nicht für vorzeichenbehaftete Ganzzahlen oder haben Probleme mit Unter- und Überläufen.
Zum Beispiel hat die akzeptierte Antwort diese Lösung:
q = 1 + ((x - 1) / y);
Wenn xNull ist, liegt ein Unterlauf vor ~0und das Ergebnis ist falsch.
Wie können Sie die Deckenrundung für vorzeichenbehaftete und vorzeichenlose Ganzzahlen korrekt implementieren und wie implementieren Sie andere Rundungsmodi wie Boden (in Richtung negative Unendlichkeit) und nach außen (von Null weg)?
Antworten
In C ++ /rundet die Divisionsoperation standardmäßig mit Abschneiden (gegen Null). Wir können das Ergebnis der Division gegen Null anpassen, um andere Rundungsmodi zu implementieren. Beachten Sie, dass, wenn die Division keinen Rest hat, alle Rundungsmodi gleich sind, da keine Rundung erforderlich ist.
In diesem Sinne können wir die verschiedenen Rundungsmodi implementieren. Bevor wir beginnen, benötigen wir jedoch eine Hilfsvorlage für die Rückgabetypen, damit wir nicht autoüberall Rückgabetypen verwenden:
#include <type_traits>
/**
* Similar to std::common_type_t<A, B>, but if A or B are signed, the result will also be signed.
*
* This differs from the regular type promotion rules, where signed types are promoted to unsigned types.
*/
template <typename A, typename B>
using common_signed_t =
std::conditional_t<std::is_unsigned_v<A> && std::is_unsigned_v<B>,
std::common_type_t<A, B>,
std::common_type_t<std::make_signed_t<A>, std::make_signed_t<B>>>;
Decke (in Richtung + ∞)
Die Deckenrundung ist identisch mit der abgeschnittenen Rundung für negative Quotienten, aber für positive Quotienten und Reste ungleich Null runden wir von Null weg. Dies bedeutet, dass wir den Quotienten für Reste ungleich Null erhöhen.
Dank if-constexprkönnen wir alles mit nur einer Funktion implementieren:
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_ceil(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// quotient is always positive
return x / y + (x % y != 0); // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
bool quotientPositive = x >= 0;
return x / sy + (x % sy != 0 && quotientPositive); // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
bool quotientPositive = y >= 0;
return sx / y + (sx % y != 0 && quotientPositive); // uint / int
}
else {
bool quotientPositive = (y >= 0) == (x >= 0);
return x / y + (x % y != 0 && quotientPositive); // int / int
}
}
Auf den ersten Blick scheinen die Implementierungen für vorzeichenbehaftete Typen teuer zu sein, da sie sowohl eine Ganzzahldivision als auch eine Modulodivision verwenden. Bei modernen Architekturen setzt die Abteilung jedoch normalerweise ein Flag, das angibt, ob ein Rest vorhanden war, und ist daher x % y != 0in diesem Fall völlig frei.
Sie fragen sich vielleicht auch, warum wir den Quotienten nicht zuerst berechnen und dann prüfen, ob der Quotient positiv ist. Dies würde nicht funktionieren, da wir während dieser Division bereits an Präzision verloren haben und diesen Test danach nicht mehr durchführen können. Zum Beispiel:
-1 / 2 = -0.5
// C++ already rounds towards zero
-0.5 -> 0
// Now we think that the quotient is positive, even though it is negative.
// So we mistakenly round up again:
0 -> 1
Boden (Richtung -∞)
Die Bodenrundung ist identisch mit dem Abschneiden für positive Quotienten, aber für negative Quotienten runden wir von Null weg. Dies bedeutet, dass wir den Quotienten für Reste ungleich Null verringern.
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_floor(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// quotient is never negative
return x / y; // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
bool quotientNegative = x < 0;
return x / sy - (x % sy != 0 && quotientNegative); // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
bool quotientNegative = y < 0;
return sx / y - (sx % y != 0 && quotientNegative); // uint / int
}
else {
bool quotientNegative = (y < 0) != (x < 0);
return x / y - (x % y != 0 && quotientNegative); // int / int
}
}
Die Implementierung ist fast identisch mit der von div_ceil.
Weg von Null
Weg von Null ist das genaue Gegenteil von abgeschnitten . Grundsätzlich müssen wir je nach Vorzeichen des Quotienten erhöhen oder verringern, aber nur, wenn es einen Rest gibt. Dies kann ausgedrückt werden durch Hinzufügen sgndes Quotienten zum Ergebnis:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Mit dieser Hilfsfunktion können wir die Rundung vollständig implementieren :
template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_up(Dividend x, Divisor y)
{
if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
// sgn is always 1
return x / y + (x % y != 0); // uint / uint
}
else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
auto sy = static_cast<std::make_signed_t<Divisor>>(y);
signed char quotientSgn = sgn(x);
return x / sy + (x % sy != 0) * quotientSgn; // int / uint
}
else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
auto sx = static_cast<std::make_signed_t<Dividend>>(x);
signed char quotientSgn = sgn(y);
return sx / y + (sx % y != 0) * quotientSgn; // uint / int
}
else {
signed char quotientSgn = sgn(x) * sgn(y);
return x / y + (x % y != 0) * quotientSgn; // int / int
}
}
Ungelöste Probleme
Leider funktionieren diese Funktionen nicht für alle möglichen Eingaben, was ein Problem ist, das wir nicht lösen können. Teilen Sie beispielsweise uint32_t{3 billion} / int32_t{1}Ergebnisse, int32_t(3 billion)die nicht darstellbar sind, mit einer 32-Bit-Ganzzahl mit Vorzeichen. In diesem Fall kommt es zu einem Unterlauf.
Die Verwendung größerer Rückgabetypen wäre eine Option für alles außer 64-Bit-Ganzzahlen, für die keine größere Alternative verfügbar ist. Daher ist es in der Verantwortung des Benutzers , um sicherzustellen , dass , wenn sie eine Zahl ohne Vorzeichen in diese Funktion übergibt, um es zu seiner signierten Darstellung entspricht.