reliably checking for overflow before addition?

Is there a reliable way to check for overflow before addition, without casting to a bigger type, or go into assembly to check the carry flag?

If I understand it correctly, the classic way -

Code:

u32 a;
if ((a+10) < 10) //overflow

is not reliable since overflow is not defined, and the compiler can and do optimize the check away.

The overflow of unsigned numbers is defined. They use modulo arithmetic.

For signed numbers, there is no portable way.

Why not something like this?

Code:

#include <climits>

int addition_will_overflow(int x, int y) {
    if(INT_MAX - x >= y) return 0;

    // the addition will overflow
    return 1;
}

That only works for positive numbers, but I'm sure you could figure something out for negative ones too . . . .

Close dwks. There are two circumstances when computing x+y (both ints) will overflow:

1) When both are positive, and INT_MAX - x < y; OR

2) When both are negative, and INT_MIN - x < y

I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).

Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.

The overflow of unsigned numbers is defined. They use modulo arithmetic.

For signed numbers, there is no portable way.

Thanks. Nice to know.

I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).

The answer is they all don't overflow?

From dwks's code and grumpy's hint -

Code:

bool addition_will_overflow(int a, int b) {
	if (a > 0 && b > 0) {
		return (INT_MAX - a) < b;
	} else if (a < 0 && b < 0) {
		return (INT_MIN - a) > b;
	}
	return false;
}

Is that it?

Originally Posted by grumpy

Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.

And I still don't understand why they made them runtime functions.
You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
They're constant, so that's far better than std's implementation.

Originally Posted by Elysia

And I still don't understand why they made them runtime functions.

There is no requirement they be runtine functions.

std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.

Originally Posted by Elysia

You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
They're constant, so that's far better than std's implementation.

Just a different way of achieving the same thing.

Originally Posted by grumpy

There is no requirement they be runtine functions.

std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.

Perhaps. But then again, perhaps not.
Do they return constant values?
If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.

Just a different way of achieving the same thing.

But it has its advantages.

Originally Posted by Elysia

Perhaps. But then again, perhaps not.
Do they return constant values?

std::numeric_limits<T>::min() and max() return the minimum and maximum finite value of the type respectively - and those values are implementation defined constants (ie in the case of int they are INT_MIN and INT_MAX respectively).

Originally Posted by Elysia

If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.

That is not true: C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.

But it has its advantages.

Other than convenience of syntax, I'd be curious to know what you consider those to be. (I exclude syntax, because the notion of "best" or "advantageous" is highly subjective when it comes to elements of syntax -- we could debate different ideas about syntax for months, and both be completely correct at the same time by some measure).

Well, maybe I am underestimating what the compiler can do, but I would still like to prefer boost's syntax, at least.

OK, let's see. The return values of numeric_limits::min() and max() are not compile-time constants from the language point of view, for the simple reason that function return values never are. This is not a performance problem, since these functions will most definitely be inlined by any even halfway decent compiler, but it matters because compile-time constants are required in some circumstances. In particular, you can't use min() and max() as array bounds or as non-type template parameters.

There are some very good reasons to make them functions. Peculiarly enough, one of those reasons is performance. Consider:

Code:

// This is <limits>

template <>
struct numeric_limits<float>
{
  static float min() { return <minimal floating point value>; }
};

This is what a specialization of numeric_limits looks like in the standard. The compiler, seeing a call of min(), would simply inline the function and find out that it's dealing with a simple literal, opening up a lot of new optimization opportunities.

Let's examine the possibilities if it's a static constant variable.

Code:

// This is <limits>

template <>
struct numeric_limits<float>
{
  static const float min = <minimal floating point value>;
};

Nope, that's an error. Inline initialization is only allowed for integral static constants.

Code:

// This is <limits>

template <>
struct numeric_limits<float>
{
  static const float min;
};

template <>
const float numeric_limits<float>::min = <minimal floating point value>;

Nope, that's another error. Specifically, you'll get linker errors from this symbol.

How about this then?

Code:

// This is <limits>

template <>
struct numeric_limits<float>
{
  static const float min;
};

// This is limits.cpp, a file linked into the compiler's precompiled standard library.

template <>
const float numeric_limits<float>::min = <minimal floating point value>;

Ah yes, that works. Only, now the constant value is no longer accessible to the compiler for further optimization. Oops.

OK, so a compiler that does cross-module optimization might be able to optimize this. If, that is, you're linking against a static version of the runtime. Definitely not if you're linking against a dynamic version.

So by converting the function to a static constant, in the belief that perhaps this is faster, you've actually made it slower.



Here's the good news: C++0x introduces the constexpr keyword, which forces the compiler to evaluate simple functions at compile time if possible. Thus, the result becomes a proper compiler-time constant expression, and you get the best of both worlds.

Originally Posted by grumpy

C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.

As CornedBee says, return results are not constants. You can't use the return result as the size to declare an array, or as a value assigned to an enum etc. As such, I'd say Elysia was correct in that they really aren't useful in Template meta-programming. It's not an oversight though, as demonstrated, there just isn't a better way.

It's not about what it could optimise, it's about what is or isn't legal C++. "Inlining of functions" in template meta-programming isn't about inlining a normal function, it's about writing a template meta-program to replace what would otherwise be a function call, to the point that there is no function call at all, both in the syntax of the entire meta-program itself and where it's used.
E.g:

Code:

template <unsigned n, unsigned b>
struct ceilLogb {
	enum { ret = ceilLogb<(n+b-1)/b, b>::ret + 1 };
}; 
template <unsigned b>
struct ceilLogb<1, b> {
  enum { ret = 0 };
};

int digits[ceilLogb<MYMAXVAL, 10>::ret];

instead of the following, which of course cannot compile:

Code:

int digits[ceil(log10(MYMAXVAL))];

constexpr sounds really cool, as it seems that it will finally enable actual function calling in template meta-programming, and presumably allow things like that second piece of code to compile!

To a point. The restrictions on constexpr functions are pretty heavy. They must consist of a single return statement. They may not call themselves recursively.
The latter really is trouble.

However, constexpr has other uses too. For example, if you make a constructor constexpr, you can have a compile-time constant instance of the class. If you further make the getters of this class constexpr, the result will stilll be compile-time constant.

The first I can understand (maybe), but the second...? Why the heavy restrictions? To make it easier for compilers?
So long as the function contains code that can be determined at compile time, it shouldn't be a problem, even if calls it recursively or return multiple things.

I think it was because they wanted a useful subset of full functionality that can be specified with sane language. If you have the feature of limited evaluation at compile time, then you have to specify in the standard how much "limited" is. If you don't, the feature is useless, because compilers will have different support, meaning that it's very hard to write portable code.