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

Question

最近，我看到了这个问题，该问题询问如何使用ceil四舍五入（向正无穷大）除以整数。不幸的是，答案要么不适用于有符号整数，要么存在下溢和溢出问题。

例如，接受的答案有这个解决方案：

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

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

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

Answer 1

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

考虑到这一点，我们可以实现不同的舍入模式。但在我们开始之前，我们需要一个返回类型的辅助模板，这样我们就不会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>>>;

天花板（朝向+？）

上限舍入与负商的截断舍入相同，但对于正商和非零余数，我们从零舍入。这意味着我们增加非零余数的商。

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

远离零

远离零与truncate正好相反。基本上，我们需要根据商的符号递增或递减，但前提是有余数。这可以表示为将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 位整数之外的所有选项的一种选择，因为没有更大的替代方案可用。因此，用户有责任确保当他们将一个无符号数传递给这个函数时，它等同于它的有符号表示。