C ++ में फर्श, छत और बाहर की ओर गोल मोड के साथ पूर्णांक विभाजित करें

Aug 16 2020

हाल ही में, मैंने इस प्रश्न को देखा जो पूछता है कि आप पूर्णांक को छत गोलाई (सकारात्मक अनंत की ओर) से कैसे विभाजित कर सकते हैं । दुर्भाग्य से जवाब या तो हस्ताक्षर किए गए पूर्णांक के लिए काम नहीं करते हैं या अंडरफ्लो और ओवरफ्लो के साथ समस्याएं हैं।

उदाहरण के लिए, स्वीकृत उत्तर में यह समाधान है:

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

जब xशून्य होता है, तो एक अंतर्प्रवाह होता है ~0और परिणाम गलत होता है।

आप कैसे लागू कर सकते हैं प्लस्तर लगाना हस्ताक्षर किए और अहस्ताक्षरित पूर्णांकों और आप कैसे लागू कर अन्य राउंडिंग की तरह मोड के लिए सही ढंग से गोलाई मंजिल और (नकारात्मक अनंत की ओर) बाहर की ओर (शून्य से दूर)?

जवाब

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

छत (प्रति + ∞)

प्लस्तर लगाना राउंडिंग के समान है काटना नकारात्मक quotients के लिए गोलाई, लेकिन सकारात्मक quotients और अशून्य शेष के लिए हम दौर शून्य से दूर। इसका मतलब है कि हम नॉनजरो अवशेषों के लिए भागफल में वृद्धि करते हैं।

इसके लिए धन्यवाद 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

मंजिल (प्रति-()

मंजिल राउंडिंग के समान है truncate सकारात्मक quotients के लिए है, लेकिन नकारात्मक quotients के लिए हम दौर शून्य से दूर। इसका मतलब है कि हम नॉनजरो अवशेषों के लिए भागफल में कमी करते हैं।

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

अनारक्षित समस्याएं

दुर्भाग्य से ये कार्य सभी संभावित आदानों के लिए काम नहीं करेंगे, जो एक समस्या है जिसे हम हल नहीं कर सकते हैं। उदाहरण के लिए, uint32_t{3 billion} / int32_t{1}परिणामों को विभाजित करना int32_t(3 billion)जिसमें 32-बिट हस्ताक्षरित पूर्णांक का उपयोग करने योग्य नहीं है। हम इस मामले में एक अंतर्प्रवाह प्राप्त करते हैं।

बड़े रिटर्न प्रकारों का उपयोग करना सब कुछ के लिए एक विकल्प होगा लेकिन 64-बिट पूर्णांक, जहां कोई बड़ा विकल्प उपलब्ध नहीं है। इसलिए, यह सुनिश्चित करने के लिए उपयोगकर्ता की जिम्मेदारी है कि जब वे इस फ़ंक्शन में एक अहस्ताक्षरित संख्या पास करते हैं, तो यह उसके हस्ताक्षरित प्रतिनिधित्व के बराबर है।