Dividi i numeri interi con le modalità floor, ceil e outward rounding in C ++
Recentemente, ho visto questa domanda che chiede come puoi dividere gli interi con arrotondamento del limite (verso l'infinito positivo). Sfortunatamente le risposte non funzionano per interi con segno o hanno problemi con underflow e overflow.
Ad esempio, la risposta accettata ha questa soluzione:
q = 1 + ((x - 1) / y);
Quando xè zero, c'è un underflow ~0e il risultato non è corretto.
Come puoi implementare correttamente l'arrotondamento ceil per interi con e senza segno e come implementare altre modalità di arrotondamento come floor (verso l'infinito negativo) e verso l'esterno (lontano da zero)?
Risposte
In C ++, l' /operazione di divisione arrotonda usando truncate (verso zero) per impostazione predefinita. Possiamo regolare il risultato della divisione verso zero per implementare altre modalità di arrotondamento. Notare che quando la divisione non ha resto, tutte le modalità di arrotondamento sono equivalenti perché non è necessario alcun arrotondamento.
Con questo in mente, possiamo implementare le diverse modalità di arrotondamento. Ma prima di iniziare, avremo bisogno di un modello di supporto per i tipi restituiti in modo da non utilizzare i autotipi restituiti ovunque:
#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 (verso + ∞)
L' arrotondamento ceil è identico all'arrotondamento troncato per quozienti negativi, ma per quozienti positivi e resto diverso da zero arrotondiamo per difetto da zero. Ciò significa che incrementiamo il quoziente per i resti diversi da zero.
Grazie a if-constexprpossiamo implementare tutto utilizzando una sola funzione:
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 prima vista, le implementazioni per i tipi con segno sembrano costose, perché usano sia una divisione intera che una divisione modulo. Tuttavia, sulle architetture moderne la divisione tipicamente imposta un flag che indica se c'era un resto, quindi x % y != 0in questo caso è completamente gratuito.
Potresti anche chiederti perché non calcoliamo prima il quoziente e poi controlliamo se il quoziente è positivo. Questo non funzionerebbe perché abbiamo già perso precisione durante questa divisione, quindi non possiamo eseguire questo test in seguito. Per esempio:
-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
Piano (verso -∞)
L' arrotondamento dei piani è identico a troncare per i quozienti positivi, ma per i quozienti negativi arrotondiamo per difetto da zero. Ciò significa che diminuiamo il quoziente per i resti diversi da 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
}
}
L'implementazione è quasi identica a quella di div_ceil.
Lontano da zero
Lontano da zero è l'esatto opposto di troncare . Fondamentalmente, dobbiamo aumentare o diminuire a seconda del segno del quoziente, ma solo se c'è un resto. Questo può essere espresso aggiungendo il sgndel quoziente al risultato:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Usando questa funzione di supporto, possiamo implementare completamente l' arrotondamento:
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
}
}
Problemi irrisolti
Purtroppo queste funzioni non funzioneranno per tutti gli input possibili, problema che non possiamo risolvere. Ad esempio, dividendo i uint32_t{3 billion} / int32_t{1}risultati in int32_t(3 billion)cui non è rappresentabile utilizzando un intero con segno a 32 bit. In questo caso otteniamo un underflow.
L'utilizzo di tipi restituiti più grandi sarebbe un'opzione per tutto tranne gli interi a 64 bit, dove non è disponibile un'alternativa più ampia. Pertanto, è responsabilità dell'utente assicurarsi che quando passa un numero non firmato a questa funzione, sia equivalente alla sua rappresentazione firmata.