Chia số nguyên với các chế độ làm tròn tầng, ceil và ra ngoài trong C ++

Aug 16 2020

Gần đây, tôi thấy câu hỏi này mà hỏi làm thế nào bạn có thể chia số nguyên với ceil tròn (hướng dương vô cực). Thật không may, các câu trả lời không hoạt động đối với số nguyên có dấu hoặc có vấn đề với dòng chảy dưới và tràn.

Ví dụ: câu trả lời được chấp nhận có giải pháp sau:

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

Khi xbằng 0, có dòng dưới đến ~0và kết quả không chính xác.

Làm thế nào bạn có thể triển khai làm tròn ceil một cách chính xác cho các số nguyên có dấu và không có dấu và làm cách nào để triển khai các chế độ làm tròn khác như sàn (theo hướng âm vô cực) và hướng ra ngoài (cách 0)?

Trả lời

3 JanSchultke Aug 16 2020 at 11:47

Trong C ++, phép toán /chia làm tròn bằng cách sử dụng truncate (về phía 0) theo mặc định. Chúng ta có thể điều chỉnh kết quả của phép chia về 0 để thực hiện các chế độ làm tròn khác. Lưu ý rằng khi phép chia không có phần dư, tất cả các chế độ làm tròn đều tương đương vì không cần làm tròn.

Với ý nghĩ đó, chúng tôi có thể thực hiện các chế độ làm tròn khác nhau. Nhưng trước khi bắt đầu, chúng ta sẽ cần một mẫu trợ giúp cho các kiểu trả về để chúng ta không sử dụng autokiểu trả về ở mọi nơi:

#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 (về phía + ∞)

Làm tròn Ceil giống với làm tròn cắt ngắn cho các thương số âm, nhưng đối với các thương số dương và phần dư khác không, chúng ta làm tròn số 0. Điều này có nghĩa là chúng tôi tăng thương số cho các phần dư khác không.

Nhờ đó if-constexpr, chúng ta có thể triển khai mọi thứ chỉ bằng một hàm duy nhất:

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

Thoạt nhìn, việc triển khai các kiểu có dấu có vẻ tốn kém, vì chúng sử dụng cả phép chia số nguyên và phép chia mô-đun. Tuy nhiên, trên bộ phận kiến ​​trúc hiện đại thường đặt một cờ cho biết liệu có phần còn lại hay không, vì vậy x % y != 0hoàn toàn miễn phí trong trường hợp này.

Bạn cũng có thể tự hỏi tại sao chúng tôi không tính toán thương số trước và sau đó kiểm tra xem thương số có dương hay không. Điều này sẽ không hoạt động vì chúng tôi đã mất độ chính xác trong quá trình phân chia này, vì vậy chúng tôi không thể thực hiện kiểm tra này sau đó. Ví dụ:

-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

Tầng (về phía -∞)

Việc làm tròn số sàn cũng giống như cắt bớt cho các thương số dương, nhưng đối với các thương số âm, chúng ta làm tròn số 0. Điều này có nghĩa là chúng tôi giảm thương số cho các phần dư khác không.

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

Việc thực hiện gần giống như của div_ceil.

Away From Zero

Away from zero hoàn toàn ngược lại với cắt ngắn . Về cơ bản, chúng ta cần tăng hoặc giảm tùy thuộc vào dấu của thương, nhưng chỉ khi có phần dư. Điều này có thể được biểu thị bằng cách thêm sgnthương số vào kết quả:

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

Sử dụng chức năng helper này, chúng tôi hoàn toàn có thể thực hiện lên làm tròn:

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

Các vấn đề chưa được giải quyết

Thật không may, các chức năng này sẽ không hoạt động cho tất cả các đầu vào có thể có, đây là một vấn đề mà chúng tôi không thể giải quyết. Ví dụ, uint32_t{3 billion} / int32_t{1}kết quả chia int32_t(3 billion)không thể biểu diễn bằng cách sử dụng số nguyên có dấu 32 bit. Chúng tôi nhận được một quy trình dưới đây trong trường hợp này.

Sử dụng các kiểu trả về lớn hơn sẽ là một tùy chọn cho mọi thứ, trừ số nguyên 64-bit, nơi không có sẵn phương án thay thế lớn hơn. Do đó, người dùng có trách nhiệm đảm bảo rằng khi họ chuyển một số không dấu vào hàm này, nó tương đương với đại diện có dấu của nó.