Dividir enteros con los modos de redondeo de piso, techo y hacia afuera en C ++
Recientemente, vi esta pregunta que pregunta cómo se pueden dividir enteros con redondeo de techo (hacia el infinito positivo). Desafortunadamente, las respuestas no funcionan para enteros firmados o tienen problemas con subdesbordamientos y desbordamientos.
Por ejemplo, la respuesta aceptada tiene esta solución:
q = 1 + ((x - 1) / y);
Cuando xes cero, hay un subdesbordamiento ~0y el resultado es incorrecto.
¿Cómo puede implementar el redondeo de techo correctamente para enteros con y sin signo y cómo implementar otros modos de redondeo como piso (hacia infinito negativo) y hacia afuera (lejos de cero)?
Respuestas
En C ++, la /operación de división se redondea utilizando truncar (hacia cero) de forma predeterminada. Podemos ajustar el resultado de la división hacia cero para implementar otros modos de redondeo. Tenga en cuenta que cuando la división no tiene resto, todos los modos de redondeo son equivalentes porque no es necesario redondear.
Con eso en mente, podemos implementar los diferentes modos de redondeo. Pero antes de comenzar, necesitaremos una plantilla auxiliar para los tipos de devolución para que no usemos autotipos de devolución en todas partes:
#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 (hacia + ∞)
El redondeo de techo es idéntico al redondeo truncado para cocientes negativos, pero para cocientes positivos y residuos distintos de cero redondeamos desde cero. Esto significa que incrementamos el cociente para los residuos distintos de cero.
Gracias a if-constexpr, podemos implementar todo usando una sola función:
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
}
}
A primera vista, las implementaciones para tipos con signo parecen costosas, porque utilizan tanto una división de enteros como una división de módulo. Sin embargo, en las arquitecturas modernas, la división generalmente establece una bandera que indica si hubo un resto, por lo que x % y != 0es completamente gratis en este caso.
Quizás también se pregunte por qué no calculamos el cociente primero y luego verificamos si el cociente es positivo. Esto no funcionaría porque ya perdimos precisión durante esta división, por lo que no podemos realizar esta prueba después. Por ejemplo:
-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
Piso (hacia -∞)
El redondeo de piso es idéntico a truncar para cocientes positivos, pero para cocientes negativos redondeamos desde cero. Esto significa que disminuimos el cociente para los residuos distintos de cero.
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 implementación es casi idéntica a la de div_ceil.
Lejos de cero
Lejos de cero es exactamente lo contrario de truncar . Básicamente, necesitamos incrementar o decrementar según el signo del cociente, pero solo si hay un resto. Esto se puede expresar sumando el sgndel cociente al resultado:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Usando esta función auxiliar, podemos implementar completamente el redondeo hacia arriba :
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
}
}
Problemas no resueltos
Desafortunadamente, estas funciones no funcionarán para todas las entradas posibles, lo cual es un problema que no podemos resolver. Por ejemplo, dividir uint32_t{3 billion} / int32_t{1}resultados en los int32_t(3 billion)que no se pueden representar mediante un entero de 32 bits con signo. En este caso tenemos un desbordamiento.
El uso de tipos de retorno más grandes sería una opción para todo menos enteros de 64 bits, donde no hay una alternativa más grande disponible. Por lo tanto, es responsabilidad del usuario asegurarse de que cuando pase un número sin firmar a esta función, sea equivalente a su representación con signo.