Diviser les entiers avec les modes d'arrondi plancher, plafond et vers l'extérieur en C ++
Récemment, j'ai vu cette question qui demande comment diviser les entiers avec un arrondi au plafond (vers l'infini positif). Malheureusement, les réponses ne fonctionnent pas pour les entiers signés ou ont des problèmes de sous-débordements et de débordements.
Par exemple, la réponse acceptée a cette solution:
q = 1 + ((x - 1) / y);
Lorsque xvaut zéro, il y a un dépassement inférieur à ~0et le résultat est incorrect.
Comment pouvez - vous mettre en œuvre Ceil arrondi correctement pour les entiers signés et non signés et comment implémentez-vous d' autres modes d'arrondi comme étage (vers l' infini négatif) et vers l' extérieur ( à l' écart de zéro)?
Réponses
En C ++, l' /opération de division arrondit à l'aide de truncate (vers zéro) par défaut. Nous pouvons ajuster le résultat de la division vers zéro pour implémenter d'autres modes d'arrondi. Notez que lorsque la division n'a pas de reste, tous les modes d'arrondi sont équivalents car aucun arrondi n'est nécessaire.
Dans cet esprit, nous pouvons implémenter les différents modes d'arrondi. Mais avant de commencer, nous aurons besoin d'un modèle d'aide pour les types de retour afin de ne pas utiliser les autotypes de retour partout:
#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>>>;
Ceil (vers + ∞)
L' arrondi au plafond est identique à l' arrondi tronqué pour les quotients négatifs, mais pour les quotients positifs et les restes différents de zéro, nous arrondissons à partir de zéro. Cela signifie que nous incrémentons le quotient pour les restes différents de zéro.
Grâce à if-constexpr, nous pouvons tout implémenter en utilisant une seule fonction:
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
}
}
À première vue, les implémentations pour les types signés semblent coûteuses, car elles utilisent à la fois une division entière et une division modulo. Cependant, sur les architectures modernes, la division définit généralement un indicateur qui indique s'il y avait un reste, donc x % y != 0est complètement libre dans ce cas.
Vous vous demandez peut-être pourquoi nous ne calculons pas d'abord le quotient, puis vérifions si le quotient est positif. Cela ne fonctionnerait pas car nous avons déjà perdu de la précision lors de cette division, nous ne pouvons donc pas effectuer ce test par la suite. Par exemple:
-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
Étage (vers -∞)
L' arrondi de plancher est identique à tronquer pour les quotients positifs, mais pour les quotients négatifs, nous arrondissons à partir de zéro. Cela signifie que nous décrémentons le quotient pour les restes différents de zéro.
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
}
}
La mise en œuvre est presque identique à celle de div_ceil.
Loin de zéro
Loin de zéro est l'exact opposé de tronquer . Fondamentalement, nous devons incrémenter ou décrémenter en fonction du signe du quotient, mais seulement s'il y a un reste. Cela peut être exprimé en ajoutant le sgndu quotient au résultat:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
En utilisant cette fonction d'assistance, nous pouvons entièrement implémenter l' arrondi:
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
}
}
Problèmes non résolus
Malheureusement, ces fonctions ne fonctionneront pas pour toutes les entrées possibles, ce qui est un problème que nous ne pouvons pas résoudre. Par exemple, la division des uint32_t{3 billion} / int32_t{1}résultats dans int32_t(3 billion)lesquels n'est pas représentable à l'aide d'un entier signé 32 bits. Nous obtenons un sous-débit dans ce cas.
L'utilisation de types de retour plus grands serait une option pour tout sauf les entiers 64 bits, où il n'y a pas d'alternative plus grande disponible. Par conséquent, il est de la responsabilité de l'utilisateur de s'assurer que lorsqu'il passe un nombre non signé dans cette fonction, il équivaut à sa représentation signée.