C ++の床、天井、および外向きの丸めモードで整数を除算します
最近、整数をセルの丸めで（正の無限大に向かって）分割する方法を尋ねるこの質問を見ました。残念ながら、答えは符号付き整数では機能しないか、アンダーフローとオーバーフローに問題があります。
たとえば、受け入れられた回答には次の解決策があります。
q = 1 + ((x - 1) / y);
ときはxゼロであり、そこにアンダーフローである~0との結果が正しくありません。
符号付き整数と符号なし整数のセル丸めを正しく実装するにはどうすればよいですか。また、床（負の無限大に向かって）や外側（ゼロから離れる方向）などの他の丸めモードをどのように実装しますか？
回答
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（+∞に向かって）
天井の丸めは、負の商の切り捨ての丸めと同じですが、正の商とゼロ以外の剰余の場合は、ゼロから丸めます。これは、ゼロ以外の剰余の商をインクリメントすることを意味します。
のおかげif-constexprで、1つの関数だけを使用してすべてを実装できます。
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
}
}
未解決の問題
残念ながら、これらの関数はすべての可能な入力に対して機能するわけではありません。これは、解決できない問題です。たとえば、32ビットの符号付き整数を使用して表現できないuint32_t{3 billion} / int32_t{1}結果を除算しますint32_t(3 billion)。この場合、アンダーフローが発生します。
より大きな戻り値の型を使用することは、64ビット整数以外のすべてのオプションであり、より大きな代替手段はありません。したがって、この関数に符号なしの数値を渡すときに、符号付きの表現と同等であることを確認するのはユーザーの責任です。