Divida inteiros com modos de piso, teto e arredondamento para fora em C ++
Recentemente, vi esta questão que pergunta como você pode dividir inteiros com arredondamento de teto (em direção ao infinito positivo). Infelizmente, as respostas não funcionam para inteiros assinados ou têm problemas com underflows e overflows.
Por exemplo, a resposta aceita tem esta solução:
q = 1 + ((x - 1) / y);
Quando x
é zero, há um estouro negativo para ~0
e o resultado está incorreto.
Como você pode implementar o arredondamento do teto corretamente para inteiros com e sem sinal e como você implementa outros modos de arredondamento como floor (em direção ao infinito negativo) e externo (longe de zero)?
Respostas
Em C ++, a /
operação de divisão é arredondada usando truncar (para zero) por padrão. Podemos ajustar o resultado da divisão para zero para implementar outros modos de arredondamento. Observe que, quando a divisão não tem resto, todos os modos de arredondamento são equivalentes porque nenhum arredondamento é necessário.
Com isso em mente, podemos implementar os diferentes modos de arredondamento. Mas antes de começarmos, precisaremos de um modelo auxiliar para os tipos de retorno, de modo que não usemos auto
tipos de retorno em todos os lugares:
#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>>>;
Teto (em direção a + ∞)
O arredondamento de teto é idêntico ao arredondamento truncado para quocientes negativos, mas para quocientes positivos e remanescentes diferentes de zero arredondamos de zero. Isso significa que incrementamos o quociente para restos diferentes de zero.
Graças a if-constexpr
, podemos implementar tudo usando apenas uma única função:
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
}
}
À primeira vista, as implementações para tipos assinados parecem caras, porque usam uma divisão inteira e uma divisão módulo. No entanto, nas arquiteturas modernas, a divisão normalmente define um sinalizador que indica se havia um resto, portanto, x % y != 0
é totalmente gratuito neste caso.
Você também pode estar se perguntando por que não calculamos o quociente primeiro e depois verificamos se o quociente é positivo. Isso não funcionaria porque já perdemos a precisão durante esta divisão, portanto, não podemos realizar este teste depois. Por exemplo:
-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
Andar (em direção a -∞)
O arredondamento de piso é idêntico ao truncamento para quocientes positivos, mas para quocientes negativos arredondamos a partir de zero. Isso significa que diminuímos o quociente para restos diferentes de zero.
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
}
}
A implementação é quase idêntica à de div_ceil
.
Longe do Zero
Longe de zero é exatamente o oposto de truncar . Basicamente, precisamos aumentar ou diminuir dependendo do sinal do quociente, mas apenas se houver um resto. Isso pode ser expresso como a adição sgn
de do quociente ao resultado:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Usando esta função auxiliar, podemos implementar totalmente o arredondamento:
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 não resolvidos
Infelizmente, essas funções não funcionarão para todas as entradas possíveis, o que é um problema que não podemos resolver. Por exemplo, dividir os uint32_t{3 billion} / int32_t{1}
resultados em int32_t(3 billion)
que não são representáveis usando um inteiro assinado de 32 bits. Temos um estouro negativo neste caso.
Usar tipos de retorno maiores seria uma opção para tudo, exceto inteiros de 64 bits, onde não há uma alternativa maior disponível. Portanto, é responsabilidade do usuário garantir que, ao passar um número sem sinal para essa função, ele seja equivalente à sua representação assinada.