หารจำนวนเต็มด้วยโหมดการปัดเศษพื้นเพดานและด้านนอกใน C ++

Aug 16 2020

เมื่อเร็ว ๆ นี้ฉันเห็นคำถามนี้ซึ่งถามว่าคุณสามารถหารจำนวนเต็มด้วยการปัดเศษceil ได้อย่างไร (ไปทางอินฟินิตี้บวก) น่าเสียดายที่คำตอบไม่สามารถใช้ได้กับจำนวนเต็มที่ลงชื่อหรือมีปัญหาเกี่ยวกับการล้นและล้น

ตัวอย่างเช่นคำตอบที่ยอมรับมีวิธีแก้ปัญหานี้:

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

เมื่อxใดที่เป็นศูนย์จะมีค่าต่ำ~0เกินไปและผลลัพธ์ไม่ถูกต้อง

คุณจะใช้การปัดเศษceilอย่างถูกต้องสำหรับจำนวนเต็มที่ลงชื่อและไม่ได้ลงนามได้อย่างไรและคุณจะใช้โหมดการปัดเศษอื่น ๆ เช่นพื้น (ไปทางอินฟินิตี้เชิงลบ) และด้านนอก (ห่างจากศูนย์) ได้อย่างไร

คำตอบ

3 JanSchultke Aug 16 2020 at 11:47

ใน 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>>>;

เพดาน (ไปทาง + ∞)

การปัดเศษเพดานจะเหมือนกับการตัดทอนการปัดเศษสำหรับผลคูณเชิงลบ แต่สำหรับผลหารบวกและเศษเหลือที่ไม่ใช่ศูนย์เราจะปัดเศษออกจากศูนย์ ซึ่งหมายความว่าเราเพิ่มผลหารสำหรับเศษเหลือที่ไม่ใช่ศูนย์

ต้องขอบคุณ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 บิตซึ่งไม่มีทางเลือกอื่นที่ใหญ่กว่า ดังนั้นจึงเป็นความรับผิดชอบของผู้ใช้ที่จะต้องตรวจสอบให้แน่ใจว่าเมื่อพวกเขาส่งหมายเลขที่ไม่ได้ลงชื่อเข้าสู่ฟังก์ชันนี้จะเทียบเท่ากับการลงนามแทน