在C ++中用下限，ceil和向外舍入模式除整数 [英] Divide integers with floor, ceil and outwards rounding modes in C++

问题描述

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

Recently, I saw this question which asks how you can divide integers with ceil rounding (towards positive infinity). Unfortunately the answers either don't work for signed integers or have problems with underflows and overflows.

例如，接受的答案具有以下解决方案：

For instance, the accepted answer has this solution:

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

当 x 为零时，〜0 ，结果不正确。

When x is zero, there is an underflow to ~0 and the the result is incorrect.

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

How can you implement ceil rounding correctly for signed and unsigned integers and how do you implement other rounding modes like floor (towards negative infinity) and outwards (away from zero)?

推荐答案

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

In C++, the / division operation rounds using truncate (towards zero) by default. We can adjust the result of division towards zero to implement other rounding modes. Note that when the division has no remainder, all rounding modes are equivalent because no rounding is necessary.

请记住，我们可以实现不同的舍入模式。
但是，在开始之前，我们需要一个用于返回类型的帮助程序模板，这样我们就不会在所有地方都使用 auto 返回类型：

With that in mind, we can implement the different rounding modes. But before we get started, we will need a helper template for the return types so that we don't use auto return types everywhere:

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

Ceil (towards +∞)

Ceil rounding is identical to truncate rounding for negative quotients, but for positive quotients and nonzero remainders we round away from zero. This means that we increment the quotient for nonzero remainders.

感谢 if-constexpr ，我们可以仅使用一个函数来实现所有功能：

Thanks to if-constexpr, we can implement everything using only a single function:

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 在这种情况下是完全免费的。

At first glance, the implementations for signed types seem expensive, because they use both an integer division and a modulo division. However, on modern architectures division typically sets a flag that indicates whether there was a remainder, so x % y != 0 is completely free in this case.

您可能还想知道为什么我们不先计算商，然后再检查商是否为正。这行不通，因为我们在这一划分过程中已经失去了精度，因此我们以后无法执行此测试。例如：

You might also be wondering why we don't compute the quotient first and then check if the quotient is positive. This wouldn't work because we already lost precision during this division, so we can't perform this test afterwards. For example:

-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（向-∞）

Floor 对于正商，舍入与 truncate 相同，但是对于负商，我们舍入为零。

Floor (towards -∞)

Floor rounding is identical to truncate for positive quotients, but for negative quotients we round away from zero. This means that we decrement the quotient for nonzero remainders.

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

实现与<$几乎相同c $ c> div_ceil 。

远离零是与 truncate 完全相反。基本上，我们需要根据商的符号递增或递减，但前提是存在余数。这可以表示为在结果上加上商的 sgn ：

Away from zero is the exact opposite of truncate. Basically, we need to increment or decrement depending on the sign of the quotient, but only if there is a remainder. This can be expressed as adding the sgn of the quotient onto the result:

template <typename Int>
constexpr signed char sgn(Int n)
{
    return (n > Int{0}) - (n < Int{0});
};

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

Using this helper function, we can fully implement up rounding:

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 {30亿} / int32_t {1} 除以得到 int32_t（30亿）使用32位带符号整数无法表示。
在这种情况下，我们会出现下溢。

Unresolved Problems

Unfortunately these functions won't work for all possible inputs, which is a problem that we can not solve. For example, dividing uint32_t{3 billion} / int32_t{1} results in int32_t(3 billion) which isn't representable using a 32-bit signed integer. We get an underflow in this case.

对于64位整数（除了没有更大的替代方法），所有类型都可以使用较大的返回类型。
因此，用户有责任确保当他们将未签名的数字传递给该函数时，它等同于其签名表示。

Using larger return types would be an option for everything but 64-bit integers, where there isn't a larger alternative available. Hence, it is the responsibility of the user to ensure that when they pass an unsigned number into this function, it is equivalent to its signed representation.

这篇关于在C ++中用下限，ceil和向外舍入模式除整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！