在 C++ 中用 floor、ceil 和向外舍入模式划分整数

Question

最近，我看到 this question 询问如何用 ceil 舍入（向正无穷大）除整数。不幸的是，答案要么不适用于有符号整数，要么存在下溢和上溢问题。

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

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

当x为零时，下溢到~0，结果不正确。

如何为有符号和无符号整数正确实现 ceil 舍入以及如何实现其他舍入模式，如 floor（朝向负数无穷大）和向外（远离零）？

Answer 1

在 C++ 中，/ 除法运算默认使用 truncate（趋向于零）。我们可以将除法的结果调整为零以实现其他舍入模式。请注意，当除法没有余数时，所有舍入方式都是等价的，因为不需要舍入。

考虑到这一点，我们可以实现不同的舍入模式。但在我们开始之前，我们需要一个 return 类型的辅助模板，这样我们就不会到处使用 auto return 类型：

#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 舍入与 truncate 负商舍入相同，但对于正商和非零余数，我们从零舍入。这意味着我们增加非零余数的商。

多亏了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

地板（朝向-∞）

对于正商，

Floor 舍入与 truncate 相同，但对于负商，我们从零舍入。这意味着我们减少非零余数的商。

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});
};

使用这个辅助函数，我们可以完全实现 up 舍入：

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 位带符号整数表示的。在这种情况下我们会遇到下溢。

使用更大的 return 类型是除了 64 位整数之外的所有选项，因为没有更大的替代方案可用。因此，用户有责任确保将无符号数传递给此函数时，它等同于其有符号表示形式。

Answer 2

我会简化并使用同类参数类型，并让用户在必要时为异构输入进行显式类型转换。这样，可能的不足和溢出就被移到了这些函数之外。当然，正常的 UB 案例适用，例如。除以零和 std::numeric_limits::min() 除以 -1 得到带符号的 T.

#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;
}

在 C++ 中用 floor、ceil 和向外舍入模式划分整数

Divide integers with floor, ceil and outwards rounding modes in C++

c++

math

integer

rounding

division

Ceil（朝向+∞）

地板（朝向-∞）

远离零

未解决的问题