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?
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.
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?
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.
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]
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.
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.
#include <iostream>
usingnamespace 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;
}
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
#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';
}
}
}
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.
@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
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).