exception handling for int overflow

[mzimmers]

I've written a routine to raise an int to a supplied power. I've never worked with exception handling; is there a way to test whether my result has overflowed the capacity of the storage element?

Thanks.

[Cubbi]

There is no mechanism to automatically generate an exception on integer overflow (there is one for floating-point overflow, but it's compiler-specific).

You cannot even automatically detect it, unless your compiler provides (an even more compiler-specific) access to the integer overflow flag of your CPU (if your CPU has such flag)

Your best bet is to use a bit of math and figure out whether your addition or squaring (assuming you're doing a worthwhile exercise where power function uses repeated squaring) is safe before doing it, or test the result afterwards, knowing what happens to integers that overflow.

[mzimmers]

Thanks for the reply. As far as how to solve this, I suppose I could store the minimum and maximum values for a 32-bit int in floats, and do my exponentiation in floats, comparing the result to my min/max values. If it's OK, I could do the exponentiation again, on the int values (to retain precision).

This sounds kind of clunky, but I imagine it would work. Thoughts?

[Mats]

What is wrong with this?

int n = 0, i = 0;
int p = -1;

int main()
{
    n = 0;
    i = 0;
    p = -1;
    cout << "Enter integer: " << endl;
    while(n > 2147483647 || n < 1)
    {
        cin >> n;
    }
    cout << "Enter power to be raised to: " << endl;
    while(p < 0 || p > 50)
    {
        cin >> p;
    }
    if(p == 0)
    {
        n = 1;
    }
    else
    {
        ++i;
        while(i < p) //This bit handles the overflow during calculation. 
        {
            if(n > 2147483647 || n < 0)
            {
                cout << "Overflow" << endl;
                main();
                break;
            }
            n = n * n;
            ++i;
        }
    }
    cout << n << endl;
    main();
    return 0;
}

If we have an overflow, we run main again. Edit: Clearer with the whole code I think.

[mzimmers]

Hey, Mats, thanks for the code. I don't understand, though, how this works. On my machine at least, if I overflow an int, the math just flows into the sign bit, possibly but necessarily producing a negative number. I don't see how using an unsigned int gets me past this problem, since it only gives me one more bit of range.

[Cubbi]

Mats wrote:

What is wrong with this?

test.cc:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
test.cc:30:38: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]
test.cc:33:22: warning: ISO C++ forbids taking address of function ‘::main’ [-pedantic]
test.cc:41:10: warning: ISO C++ forbids taking address of function ‘::main’ [-pedantic]

[Mats]

oh lol n is supposed to be SIGNED. All those things should just be int. Compiles without error or warning for me and runs with no problem.

[Cheraphy]

What compiler set are you using?

[Mats]

test.cc:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
test.cc:30:38: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

These two warnings obviously vanish when you set them to 'int'. I don't have pedantic checking on, although you could get rid of the pedantic error by just sticking this in a function other than main and calling that.

And I use MinGW.

[mzimmers]

Xander: if you're asking me, I'm using gcc (don't know which version), but this code needs to be highly portable, so I can't take advantage of any compiler-specific features.

[mzimmers]

Mats: your program wasn't working properly; it didn't retain the original value of n for the exponentiation. I made a couple of changes:

#include <iostream>

using namespace std;

int n = 0, i = 0;
int p = -1;
int	result;

int main()
{
	int n = 0, i = 0;
	int p = -1;
	int	result;

	cout << "Enter integer: " << flush;
	while(n > 2147483647 || n < 1)
	{
		cin >> n;
	}
	cout << "Enter power to be raised to: " << flush;
	while(p < 0 || p > 50)
	{
		cin >> p;
	}
	if (p == 0)
	{
		n = 1;
	}
	else
	{
		result = 1;
		while(i < p) //This bit handles the overflow during calculation.
		{
			if(n > 2147483647 || n < 0)
			{
				cout << "Overflow" << endl;
				main();
				break;
			}
			result *= n;
			++i;
		}
	}
	cout << result << endl;
	main();
	return 0;
}

This works for in-range values, but doesn't catch an overflow. It also doesn't work for negative numbers.

It's a good start, though...maybe someone can improve upon it.

[Cubbi]

When I said a bit of math I meant a bit of math:

Multiplication of two numbers n and r will only overflow an int with d non-sign bits if
n * r >= 2^d
taking base-2 logarithms
log2(n) + log2(r) >= d

The function that raises n to the power of p will only overflow out of a int with d bits if
n ^ p >= 2 ^ d
take base-2 logarithm
log2(n) * p >= d


If you don't care about CPU time, you could do just one test: std::log2(n) * p >= numeric_limits<int>::digits, but it doesn't make a lot of sense bringing in the floating-point arithmetic. log2(n), rounded to integer, is simply the position of the highest bit set.

However, testing jut the highest bit set will not catch the numbers whose log2(n) is greater than the threshold by less than 1, so this needs to be tested within the function, not before

so,

#include <iostream>
#include <stdexcept>
#include <limits>

// tons of ways to make this faster on the bithacks page
int maxbitpos(int n) // n is positive due to test in mypow()
{
    int p = 0;
    while(n >>= 1) ++p;
    return p;
}

// doing power as n*n*n*n*n*... is as pointless as bubble sort
int mypow(int n, int p)
{
    if(p<0) 
        throw std::runtime_error("negative power not supported");
    if(p==0) return 1; // not hanlding negative powers for this
    if(p==1) return n; // avoid overflow in squaring

    if(2*maxbitpos(n) >= std::numeric_limits<int>::digits)
        throw std::overflow_error("integer overflow in pow()");

    int r = mypow(n*n, p/2);

    if(p&1) {
        if(maxbitpos(n) + maxbitpos(r) >= std::numeric_limits<int>::digits)
            throw std::overflow_error("integer overflow in pow()");
        return n*r;
    } else {
        return r;
    }
}

int main()
{
    for(;;) {
        std::cout << "integer: ";
        int n;
        std::cin >> n;

        std::cout << "power: ";
        int p;
        std::cin >> p;

        if(!std::cin) break; // quit on EOF

        try {
            std::cout << "result = " << mypow(n, p) << '\n';
        } catch(const std::exception& e) {
            std::cout << "could not pow(): " << e.what() << '\n';
        }
    }
}

demo: http://ideone.com/x94na

edit: fixed bugs

[mzimmers]

Thanks, Cubbi. Your math abilities far exceed mine; I'd never have come up with that on my own. I appreciate your help.

[bluecoder]

can some one tell me what does

while(n >>= 1) ++p;

do ?

[mzimmers]

It's finding the most significant non-zero bit in n, and storing it in p. Specifically, it's right-shifting n by 1 bit, and testing it for zero/non-zero status.

[naraku9333]

@bluecoder
I believe it is counting the number of bits in n. If n originally is 21485900 after shifts n will be 2148590,214859,
21485,2148,2148,214,21,2,0. p should equal 8.

[bluecoder]

thanks nzinners .. i got it cleared by running the program .

@naraku9333
it does not shift the bits but it dived the number and checks if the remainder is 1.


but ... thanks both of you ..it cleared what is going on ,,

[naraku9333]

@bluecoder
I dont know what I was thinking yesterday, but it does shift the bits right by 1 bit, if n is not 0 add 1 to p counting the bits. The right shift by 1 effectively divides by 2(IIRC).

[bluecoder]

@naraku9333

you are right .. sorry for that ..
i right shift by one bit ( means divides by 2).

Thanks again .

[SIK]

Hi mzimmers,

Do I understand correctly? Do you want to raise some int x to some int y and determine if result stored in int z has overflowed?