Sum function with return type large enough to hold

问题:

It's a question from C++ Primer Chapter 16.2.3 (question 16.41):

Write a version of sum with a return type that is guaranteed to be large enough to hold the result of the addition.

I'm sure there might be some rather obscure STL function that can get this job done, but in the context of the chapter it introduces Standard Type Transformation Templates such as remove_reference<T> and make_signed<T> which I'm sure it intends for me to use to accomplish this, in conjunction with trailing return types. The best I can do is:

template <typename It> auto sum(It first, It second) -> typename make_unsigned<It>::type {
    return first+second;
}

This almost answers the question but not quite, it doesn't account for that fact that I could pass two unsigned ints which add to go outside the range of values that an unsigned int can hold (and so loops back down to zero). As far as I can tell the transformation templates can't help with that issue, is it somehow possible to deduce the return type as the next largest integral type up from the integral type deduced from the passed arguments?

回答1:

Since you want to do this at compile time, there is no way of knowing the value of the arguments the function will be invoked with. So you should protect agains overflowing at compile time, and the most obvious thing that comes to my mind is using a promotion trait class:

#include <iostream>
#include <limits>

template<typename T>
struct promote;

template<> // and so on for all types that you want to promote
struct promote<unsigned int> // type to be promoted from
{
    using type = unsigned long int; // type to be promoted to
};

// helper a la C++14
template<typename T>
using promote_t = typename promote<T>::type;

template <typename It> 
auto my_sum(It first, It second) -> promote_t<It>
{
    return static_cast<promote_t<It>>(first) + second; // promotion
}

int main()
{
    unsigned int a = std::numeric_limits<unsigned int>::max();
    unsigned int b = std::numeric_limits<unsigned int>::max();

    auto c = my_sum(a, b); // type is promoted to unsigned long int
    std::cout << "a = " << a << std::endl;
    std::cout << "b = " << b << std::endl;
    std::cout << "a + b = " << c << std::endl;
}

Live on Coliru

回答2:

Expanding upon @vsoftco's answer, this would be a more portable way to define the promote classes, also taking into account the case where both arguments are negative:

#include <cstdint>
#include <type_traits>
#include <limits>

template<std::size_t, bool> struct promote;

template<> struct promote<sizeof(std::uint8_t ), false> { using type = std::uint16_t; };
template<> struct promote<sizeof(std::uint16_t), false> { using type = std::uint32_t; };
template<> struct promote<sizeof(std::uint32_t), false> { using type = std::uint64_t; };

template<> struct promote<sizeof(std::int8_t ), true> { using type = std::int16_t; };
template<> struct promote<sizeof(std::int16_t), true> { using type = std::int32_t; };
template<> struct promote<sizeof(std::int32_t), true> { using type = std::int64_t; };

template<typename T> using promote_t = typename promote<sizeof(T), std::is_signed<T>::value>::type;

template <typename T>
promote_t<T> my_sum(T first, T second)
{
    return static_cast<promote_t<T>>(first) + second; // promotion
}

void test()
{
    using namespace std;
    auto a = numeric_limits<int>::min();
    cout << a << " + " << a << " = " << my_sum(a, a) << endl;

    auto b = numeric_limits<unsigned int>::max();
    cout << b << " + " << b << " = " << my_sum(b, b) << endl;
}

回答3:

I decided to add a way to pick the next largest integral type based on the size of the type. It checks if the type is signed, and if so, makes it unsigned. Otherwise, it checks the unsigned types beginning with unsigned char to find the smallest type that is larger than the current one. It fails a static_assert if there is no larger type. It works like this:

int main()
{
    int a = 0, b = 0;
    sum(a, b); //return type is unsigned int
    unsigned int c = 0, d = 0;
    sum(c, d); //return type is unsigned long long on my platform
    unsigned long long e = 0, f = 0;
    sum(e, f); //error
}

The full code is below. It's not the prettiest thing in the world, but I thought it was an interesting experiment.

#include <type_traits>
#include <tuple>
#include <cstddef>

typedef std::tuple<unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long> type_list;

template <typename, std::size_t>
struct get_larger_type;

template <bool B_, std::size_t S_, typename T_, typename... Ts_>
struct picker
{
    typedef T_ type;
};

template <std::size_t S_, typename T_, typename... Ts_>
struct picker<false, S_, T_, Ts_...>
{
    typedef typename get_larger_type<std::tuple<Ts_...>, S_>::type type;
};

template <typename T_, typename... Ts_, std::size_t S_>
struct get_larger_type<std::tuple<T_, Ts_...>, S_>
{
    typedef typename picker<(sizeof(T_) > S_), S_, T_, Ts_...>::type type;
};
template <std::size_t S_>
struct get_larger_type<std::tuple<>, S_>
{
    //Or if you want to use a multiprecision library, edit this to use that.
    static_assert(S_ != S_, "Foolish mortal you tread on the domain of gods!");
    typedef void type;
};

template <bool, typename T_>
struct pick_promotion
{
    typedef typename std::make_unsigned<T_>::type type;
};

template <typename T_>
struct pick_promotion<true, T_>
{
    typedef typename get_larger_type<type_list, sizeof(T_)>::type type;
};

template <typename T_>
typename pick_promotion<std::is_unsigned<T_>::value, T_>::type sum(T_ a, T_ b)
{
    return static_cast<T_>(a) + static_cast<T_>(b);
}

回答4:

with a return type that is guaranteed to be large enough to hold the result of the addition.

Your easy option is to use an arbitrary precision math package.

Your slightly harder option is to write an arbitrary precision arithmetic add.

I have some code that uses a package, but I can't find it at the moment. Will update when I find it. Easy to use.

Update: found it

package called gmpxx.h. (I think boost also has a suitable class or 2)

---

With uint64_t, factorial 93 (or maybe 94?) causes wrap around.

93!  
  1,156,772,507,081,641,574,759,205,162,306,240,436,214,753,229,576,413,535,186,142,281,213,246,807,
121,467,315,215,203,289,516,844,845,303,838,996,289,387,078,090,752,000,000,000,000,000,000,000

---

With mpz_class,

1000!  
402,387,260,077,093,773,543,702,433,923,003,985,719,374,864,210,714,632,543,799,910,429,938,512,398,
629,020,592,044,208,486,969,404,800,479,988,610,197,196,058,631,666,872,994,808,558,901,323,829,669,
944,590,997,424,504,087,073,759,918,823,627,727,188,732,519,779,505,950,995,276,120,874,975,462,497,
043,601,418,278,094,646,496,291,056,393,887,437,886,487,337,119,181,045,825,783,647,849,977,012,476,
632,889,835,955,735,432,513,185,323,958,463,075,557,409,114,262,417,474,349,347,553,428,646,576,611,
667,797,396,668,820,291,207,379,143,853,719,588,249,808,126,867,838,374,559,731,746,136,085,379,534,
524,221,586,593,201,928,090,878,297,308,431,392,844,403,281,231,558,611,036,976,801,357,304,216,168,
747,609,675,871,348,312,025,478,589,320,767,169,132,448,426,236,131,412,508,780,208,000,261,683,151,
027,341,827,977,704,784,635,868,170,164,365,024,153,691,398,281,264,810,213,092,761,244,896,359,928,
705,114,964,975,419,909,342,221,566,832,572,080,821,333,186,116,811,553,615,836,546,984,046,708,975,
602,900,950,537,616,475,847,728,421,889,679,646,244,945,160,765,353,408,198,901,385,442,487,984,959,
953,319,101,723,355,556,602,139,450,399,736,280,750,137,837,615,307,127,761,926,849,034,352,625,200,
015,888,535,147,331,611,702,103,968,175,921,510,907,788,019,393,178,114,194,545,257,223,865,541,461,
062,892,187,960,223,838,971,476,088,506,276,862,967,146,674,697,562,911,234,082,439,208,160,153,780,
889,893,964,518,263,243,671,616,762,179,168,909,779,911,903,754,031,274,622,289,988,005,195,444,414,
282,012,187,361,745,992,642,956,581,746,628,302,955,570,299,024,324,153,181,617,210,465,832,036,786,
906,117,260,158,783,520,751,516,284,225,540,265,170,483,304,226,143,974,286,933,061,690,897,968,482,
590,125,458,327,168,226,458,066,526,769,958,652,682,272,807,075,781,391,858,178,889,652,208,164,348,
344,825,993,266,043,367,660,176,999,612,831,860,788,386,150,279,465,955,131,156,552,036,093,988,180,
612,138,558,600,301,435,694,527,224,206,344,631,797,460,594,682,573,103,790,084,024,432,438,465,657,
245,014,402,821,885,252,470,935,190,620,929,023,136,493,273,497,565,513,958,720,559,654,228,749,774,
011,413,346,962,715,422,845,862,377,387,538,230,483,865,688,976,461,927,383,814,900,140,767,310,446,
640,259,899,490,222,221,765,904,339,901,886,018,566,526,485,061,799,702,356,193,897,017,860,040,811,
889,729,918,311,021,171,229,845,901,641,921,068,884,387,121,855,646,124,960,798,722,908,519,296,819,
372,388,642,614,839,657,382,291,123,125,024,186,649,353,143,970,137,428,531,926,649,875,337,218,940,
694,281,434,118,520,158,014,123,344,828,015,051,399,694,290,153,483,077,644,569,099,073,152,433,278,
288,269,864,602,789,864,321,139,083,506,217,095,002,597,389,863,554,277,196,742,822,248,757,586,765,
752,344,220,207,573,630,569,498,825,087,968,928,162,753,848,863,396,909,959,826,280,956,121,450,994,
871,701,244,516,461,260,379,029,309,120,889,086,942,028,510,640,182,154,399,457,156,805,941,872,748,
998,094,254,742,173,582,401,063,677,404,595,741,785,160,829,230,135,358,081,840,096,996,372,524,230,
560,855,903,700,624,271,243,416,909,004,153,690,105,933,983,835,777,939,410,970,027,753,472,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000