Как правильно реализовать целочисленное округление?

Question

Как правильно реализовать целочисленное округление?

Очень часто нужно делить целые числа, но результат округляется в большую сторону, а не в меньшую сторону. Некоторое время я использовал следующую функцию для этой мини-идиомы:

template <typename S, typename T>
constexpr inline S div_rounding_up(const S& dividend, const T& divisor)
{
return (dividend + divisor - 1) / divisor;
}

Это имеет (по крайней мере) следующие недостатки, или то, что можно рассматривать как недостатки:

Пока он работает «как обещано» с отрицательными операндами — он называется div_rounding_up — вероятно, было бы более разумно иметь такую функцию, округленную от нуля, так как x / y для негатива x и положительный y округляет до нуля. Другими словами, может быть, я должен реализовать div_rounding_away_from_zero, который был бы коммутативным с инверсией: auto f = [&y](const S& x) { return div_rounding_away_from_zero(x,y); } мы бы хотели иметь f(-x) == -f(x),
Переполнение в конце домена S,
Возможно странное поведение, когда sizeof(S) > sizeof(T),
длинное имя функции …

Хотя вы легко можете придумать способы решения каждого из них, они могут привести к другим возможным недостаткам, таким как условные обозначения в коде или зависимость от расчета модуля, который может быть дорогостоящим.

Так есть ли «правильный путь» для реализации этого? Под «правильным» я подразумеваю семантически приятный, эффективный, избегающий многих из перечисленных выше недостатков и, надеюсь, широко используемый.

Заметки:

Если вы считаете, что функция должна строго содержаться, чтобы работать только с неотрицательными аргументами, скажем так. Это было бы немного проблематичным ИМХО, так как мы не хотим ограничивать типы неподписанными, и мы не хотим проверять знаки операндов. Это похоже на то, для чего я бы использовал контакт — а в C ++ их пока нет.
Использует std::div а варианты тут хорошая идея?
Производительность важнее, чем удобочитаемость. В худшем случае можно добавить комментарий.
Код не должен быть привязан к конкретной архитектуре (но если вы хотите использовать ifdef-else для разных архитектур, будьте моим гостем).
Код не должен предполагать конкретный компилятор.

0

c++idiomatic integer-division number-rounding

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Возможно странное поведение, когда sizeof(S) > sizeof(T),

Вероятно, было бы лучше использовать аргумент одного типа и позволить пользователю иметь дело с преобразованием, которое он хочет. Этот подход используется математическими функциями стандартной библиотеки.

Переполнение около конца домена S.

Округление на основе остатка не имеет этой проблемы.

опора на расчет модуля, который может быть дорогим.

Вы уже рассчитываете деление, которое дорого. На x86, по крайней мере, инструкция деления хранит остаток в регистре, и достойная реализация std::div буду использовать это. Современный компилятор даже сможет оптимизировать явное использование операций деления и остатка.

Использует std::div а варианты тут хорошая идея?

Конечно.

Если вы считаете, что функция должна строго содержаться, чтобы работать только с неотрицательными аргументами, скажем так.

Я думаю, что вы должны по крайней мере требовать, чтобы аргументы имели одинаковый знак. Направление округления оператора деления и остатка (также по расширению std::div поскольку C ++ 11) определяется реализацией. С этим требованием нет никакой разницы между округлением от нуля и округлением вверх, поскольку ни один из поддерживаемых результатов не является отрицательным.

template <typename T> // single type argument
constexpr T           // constexpr implies inline
div_round_up
(const T& dividend, const T& divisor)
{
// no overflows, only 1 expensive operation
std::div_t dv = std::div(dividend, divisor);
return dv.quot + (!!dv.rem);
}

1