Разделение целых чисел с помощью режимов округления floor, ceil и наружу в C ++
Недавно я увидел этот вопрос, в котором спрашивается, как можно делить целые числа с помощью округления ceil (в сторону положительной бесконечности). К сожалению, ответы либо не работают для целых чисел со знаком, либо возникают проблемы с недополнением и переполнением.
Например, в принятом ответе есть такое решение:
q = 1 + ((x - 1) / y);
Когда xравно нулю, происходит потеря значимости ~0и результат неверен.
Как можно правильно реализовать округление ceil для целых чисел со знаком и без знака и как реализовать другие режимы округления, такие как пол (в сторону отрицательной бесконечности) и наружу (от нуля)?
Ответы
В C ++ /операция деления по умолчанию округляется с использованием усечения (в сторону нуля). Мы можем настроить результат деления в сторону нуля, чтобы реализовать другие режимы округления. Обратите внимание, что когда от деления нет остатка, все режимы округления эквивалентны, потому что округление не требуется.
Имея это в виду, мы можем реализовать различные режимы округления. Но прежде чем мы начнем, нам понадобится вспомогательный шаблон для возвращаемых типов, чтобы мы не использовали autoвозвращаемые типы везде:
#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 (в сторону + ∞)
Округление Ceil идентично округлению с усечением для отрицательных частных, но для положительных частных и ненулевых остатков мы округляем от нуля. Это означает, что мы увеличиваем частное для ненулевых остатков.
Благодаря if-constexpr, мы можем реализовать все, используя только одну функцию:
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
}
}
На первый взгляд реализации для знаковых типов кажутся дорогими, потому что они используют как целочисленное деление, так и деление по модулю. Однако в современных архитектурах подразделение обычно устанавливает флаг, указывающий, был ли остаток, поэтому x % y != 0в этом случае он полностью бесплатен.
Вам также может быть интересно, почему мы сначала не вычисляем частное, а затем проверяем, является ли оно положительным. Это не сработает, потому что мы уже потеряли точность во время этого деления, поэтому мы не можем выполнить этот тест впоследствии. Например:
-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
Этаж (в сторону -∞)
Полное округление идентично усечению для положительных частных, но для отрицательных частных мы округляем от нуля. Это означает, что мы уменьшаем частное для ненулевых остатков.
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
}
}
Реализация практически идентична реализации div_ceil.
Вдали от нуля
Отсутствие нуля - полная противоположность усечению . По сути, нам нужно увеличивать или уменьшать в зависимости от знака частного, но только при наличии остатка. Это можно выразить как добавление sgnчастного к результату:
template <typename Int>
constexpr signed char sgn(Int n)
{
return (n > Int{0}) - (n < Int{0});
};
Используя эту вспомогательную функцию, мы можем в полной мере реализовать до округления:
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
}
}
Нерешенные проблемы
К сожалению, эти функции не будут работать для всех возможных входов, и это проблема, которую мы не можем решить. Например, деление uint32_t{3 billion} / int32_t{1}результатов int32_t(3 billion)невозможно представить с помощью 32-разрядного целого числа со знаком. В этом случае мы получаем недополнение.
Использование более крупных возвращаемых типов было бы вариантом для всего, кроме 64-битных целых чисел, где нет более крупной альтернативы. Следовательно, пользователь несет ответственность за то, чтобы при передаче беззнакового числа в эту функцию оно было эквивалентно его подписанному представлению.