在C++中用地板、细胞和向外四舍五入模式划分整数

Question

最近，我看到了this question，它问你如何用细胞四舍五入(向正无穷远方向)来划分整数。不幸的是，答案要么不适用于有符号整数，要么有问题在下面和溢出。

例如，accepted answer有这样的解决方案：

q = 1 + ((x - 1) / y);

当x为零时，会有一个向下流到~0，结果是不正确的。

如何正确地实现带符号整数和无符号整数的ceil四舍五入，以及如何实现其他舍入模式，如地板(向负无穷大)和向外(远离零)？

Answer 1

在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位整数外，使用更大的返回类型将是一种选择，因为在这里没有更大的可供选择的选项。因此，用户有责任确保当他们将一个无符号的数字传递给这个函数时，它等同于它的有符号表示。

Answer 2

如果有必要，我将简化和使用同构参数类型，并让用户为异构输入进行显式类型转换。这样，可能的下溢和溢出就移到这些函数之外.当然，正常的UB病例也适用，例如。除以零，std::numeric_limits::min()除以签名T的-1。

#include <type_traits>

//Division round up, aka take the ceiling, aka round toward positive infinity, eg. -1.5 -> -1, 1.5 -> 2
template<typename T>
    requires std::is_integral_v<T>
constexpr T divRndUp(T a, T b) noexcept
{
    if constexpr (std::is_unsigned_v<T>)
        return a / b + (a % b != 0);
    else
        return a / b + (a % b != 0 && ((a < 0) == (b < 0)));
}

//Division round down, aka take the floor, aka round toward negative infinity, eg. -1.5 -> -2, 1.5 -> 1
template<typename T>
    requires std::is_integral_v<T>
constexpr T divRndDwn(T a, T b) noexcept
{
    if constexpr (std::is_unsigned_v<T>)
        return a / b;
    else
        return a / b - (a % b != 0 && ((a < 0) != (b < 0)));
}

//Division round out, aka round out away from zero, aka round toward infinity, eg. -1.5 -> -2, 1.5 -> 2
template<typename T>
    requires std::is_integral_v<T>
constexpr T divRndOut(T a, T b) noexcept
{
    if constexpr (std::is_unsigned_v<T>)
        return a / b + (a % b != 0);
    else
        return a / b + (a % b != 0 && ((a < 0) == (b < 0))) - (a % b != 0 && ((a < 0) != (b < 0)));
}

//Division round in, aka truncate, aka round in toward zero, aka round away from infinity, eg. -1.5 -> -1, 1.5 -> 1
template<typename T>
    requires std::is_integral_v<T>
constexpr T divRndIn(T a, T b) noexcept
{
    return a / b;
}