c++ - How to detect integer overflow? -
i writing program in c++ find solutions of ab = c, a, b , c use digits 0-9 once. program looped on values of a , b, , ran digit-counting routine each time on a, b , ab check if digits condition satisfied.
however, spurious solutions can generated when ab overflows integer limit. ended checking using code like:
unsigned long b, c, c_test; ... c_test=c*b; // possible overflow if (c_test/b != c) {/* there has been overflow*/} else c=c_test; // no overflow is there better way of testing overflow? know chips have internal flag set when overflow occurs, i've never seen accessed through c or c++.
there is way determine whether operation overflow, using positions of most-significant one-bits in operands , little basic binary-math knowledge.
for addition, 2 operands result in (at most) 1 bit more largest operand's highest one-bit. example:
bool addition_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestonebitposition(a), b_bits=highestonebitposition(b); return (a_bits<32 && b_bits<32); } for multiplication, 2 operands result in (at most) sum of bits of operands. example:
bool multiplication_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestonebitposition(a), b_bits=highestonebitposition(b); return (a_bits+b_bits<=32); } similarly, can estimate maximum size of result of a power of b this:
bool exponentiation_is_safe(uint32_t a, uint32_t b) { size_t a_bits=highestonebitposition(a); return (a_bits*b<=32); } (substitute number of bits target integer, of course.)
i'm not sure of fastest way determine position of highest one-bit in number, here's brute-force method:
size_t highestonebitposition(uint32_t a) { size_t bits=0; while (a!=0) { ++bits; a>>=1; }; return bits; } it's not perfect, that'll give idea whether 2 numbers overflow before operation. don't know whether faster checking result way suggested, because of loop in highestonebitposition function, might (especially if knew how many bits in operands beforehand).
Comments
Post a Comment