Dzielenie liczb całkowitych z trybami zaokrąglania dolnego, górnego i zewnętrznego w C ++
Ostatnio widziałem to pytanie , które zadaje, jak można dzielić liczby całkowite z CEIL zaokrąglenia (w kierunku dodatnim nieskończoności). Niestety odpowiedzi albo nie działają dla liczb całkowitych ze znakiem, albo mają problemy z niedomiarami i przepełnieniami.
Na przykład zaakceptowana odpowiedź ma następujące rozwiązanie:
q = 1 + ((x - 1) / y);
Kiedy xwynosi zero, występuje niedomiar ~0i wynik jest nieprawidłowy.
Jak można zaimplementować ceil zaokrąglenie poprawnie podpisanych i niepodpisanych liczb całkowitych i jak zaimplementować inne tryby zaokrąglania jak piętrze (w kierunku ujemnym nieskończoności) oraz na zewnątrz (od zera)?
Odpowiedzi
W C ++ /operacja dzielenia jest domyślnie zaokrąglana przy użyciu obcięcia (w kierunku zera). Możemy dostosować wynik dzielenia do zera, aby zaimplementować inne tryby zaokrąglania. Zauważ, że gdy z dzielenia nie ma reszty, wszystkie tryby zaokrąglania są równoważne, ponieważ zaokrąglanie nie jest konieczne.
Mając to na uwadze, możemy zaimplementować różne tryby zaokrąglania. Ale zanim zaczniemy, będziemy potrzebować szablonu pomocniczego dla typów zwracanych, aby nie autowszędzie używać typów zwracanych:
#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>>>;
Pułap (w kierunku + ∞)
Zaokrąglanie do pułapu jest identyczne jak zaokrąglanie obcięte dla ilorazów ujemnych, ale dla ilorazów dodatnich i reszt niezerowych zaokrąglamy od zera. Oznacza to, że zwiększamy iloraz resztek niezerowych.
Dzięki temu if-constexprwszystko możemy zaimplementować używając tylko jednej funkcji:
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
}
}
Na pierwszy rzut oka implementacje typów ze znakiem wydają się drogie, ponieważ używają zarówno dzielenia liczb całkowitych, jak i dzielenia modulo. Jednak w przypadku nowoczesnych architektur podział zazwyczaj ustawia flagę wskazującą, czy pozostała część, więc x % y != 0w tym przypadku jest całkowicie bezpłatny.
Możesz się również zastanawiać, dlaczego najpierw nie obliczamy ilorazu, a następnie sprawdzamy, czy jest on dodatni. To nie zadziała, ponieważ straciliśmy już precyzję podczas tego podziału, więc nie możemy później przeprowadzić tego testu. Na przykład:
-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
Podłoga (w kierunku -∞)
Zaokrąglanie podłogi jest identyczne z obcięciem dla ilorazów dodatnich, ale dla ilorazów ujemnych zaokrąglamy od zera. Oznacza to, że zmniejszamy iloraz reszt niezerowych.
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
}
}
Implementacja jest prawie identyczna jak w przypadku div_ceil.
Daleko od zera
Daleko od zera jest dokładnym przeciwieństwem obcięcia . Zasadniczo musimy zwiększać lub zmniejszać w zależności od znaku ilorazu, ale tylko wtedy, gdy jest reszta. Można to wyrazić jako dodanie sgnilorazu do wyniku:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Korzystając z tej funkcji pomocniczej, możemy w pełni zaimplementować zaokrąglanie w górę :
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
}
}
Nierozwiązane problemy
Niestety te funkcje nie będą działać dla wszystkich możliwych wejść, co jest problemem, którego nie możemy rozwiązać. Na przykład dzielenie uint32_t{3 billion} / int32_t{1}wyników, int32_t(3 billion)których nie można przedstawić za pomocą 32-bitowej liczby całkowitej ze znakiem. W tym przypadku otrzymujemy niedomiar.
Używanie większych typów zwracanych byłoby opcją dla wszystkiego oprócz 64-bitowych liczb całkowitych, gdzie nie ma dostępnej większej alternatywy. W związku z tym na użytkowniku spoczywa odpowiedzialność za upewnienie się, że przekazanie liczby bez znaku do tej funkcji jest równoważne jej podpisanej reprezentacji.