exception handling for int overflow

Pages: 12
Dec 23, 2011 at 2:33am
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.
Dec 23, 2011 at 3:23am
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.



Dec 23, 2011 at 3:47am
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?
Dec 23, 2011 at 3:49am
What is wrong with this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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.
Last edited on Dec 23, 2011 at 5:02am
Dec 23, 2011 at 4:04am
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.
Dec 23, 2011 at 4:51am
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]
Dec 23, 2011 at 5:02am
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.
Dec 23, 2011 at 5:04am
What compiler set are you using?
Dec 23, 2011 at 5:07am
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.
Dec 23, 2011 at 5:08am
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.
Dec 23, 2011 at 5:24am
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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.
Dec 23, 2011 at 6:01am
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,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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
Last edited on Dec 23, 2011 at 2:20pm
Dec 23, 2011 at 11:30pm
Thanks, Cubbi. Your math abilities far exceed mine; I'd never have come up with that on my own. I appreciate your help.
Dec 24, 2011 at 6:16pm
can some one tell me what does

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

do ?
Dec 24, 2011 at 6:21pm
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.
Dec 24, 2011 at 6:41pm
@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.
Dec 25, 2011 at 9:41am
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 ,,
Dec 25, 2011 at 5:11pm
@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).
Dec 25, 2011 at 5:45pm
@naraku9333

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

Thanks again .
Dec 25, 2011 at 11:34pm
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?
Pages: 12