I was writing a program in C++ to find all solutions of ab = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a digit-counting routine each time on a, b and ab to check if the digits condition was satisfied.
However, spurious solutions can be generated when ab overflows the integer limit. I ended up checking for this using code like:
unsigned long b, c, c_test;
...
c_test=c*b; // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test; // No overflow
Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.
Beware that signed int overflow is undefined behaviour in C and C++, and thus you have to detect it without actually causing it. For signed int overflow before addition, see Detecting signed overflow in C/C++.
This question is related to
c++
c
integer-overflow
You can't access the overflow flag from C/C++.
I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.
Look at info as and info gcc.
A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.
MSalter's answer is a good idea.
If the integer calculation is required (for precision), but floating point is available, you could do something like:
uint64_t foo(uint64_t a, uint64_t b) {
double dc;
dc = pow(a, b);
if (dc < UINT_MAX) {
return (powu64(a, b));
}
else {
// Overflow
}
}
Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.
A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.
Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.
MSalter's answer is a good idea.
If the integer calculation is required (for precision), but floating point is available, you could do something like:
uint64_t foo(uint64_t a, uint64_t b) {
double dc;
dc = pow(a, b);
if (dc < UINT_MAX) {
return (powu64(a, b));
}
else {
// Overflow
}
}
Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).
The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:
long lng;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
printf ("%li\n", lng);
}
Adding overflow checking the way that I described results in this:
long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
if (lng <= lng_prev)
{
printf ("Overflow: %i\n", n);
/* Do whatever you do in the event of overflow. */
}
printf ("%li\n", lng);
lng_prev = lng;
}
It works for unsigned values as well as both positive and negative signed values.
Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the <= sign to make it >=, assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).
Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.
CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.
The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.
The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers. To use that instruction from C, one can write the following code in a 64-bit program (GCC):
unsigned long checked_imul(unsigned long a, unsigned long b) {
unsigned __int128 res = (unsigned __int128)a * b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}
For a 32-bit program, one needs to make the result 64 bit and parameters 32 bit.
An alternative is to use compiler-dependent intrinsic to check the flag register. GCC documentation for overflow intrinsic can be found from 6.56 Built-in Functions to Perform Arithmetic with Overflow Checking.
Another interesting tool is IOC: An Integer Overflow Checker for C/C++.
This is a patched Clang compiler, which adds checks to the code at compile time.
You get output looking like this:
CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.
You'll probably find that this is more efficient than doing the division as you've done in your example.
Oh, and it'll work in both C and C++ (as you've tagged the question with both).
Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:
FPE_INTOVF_TRAPInteger overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).
A bit of a shame really.
If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.
uint8_t x, y; /* Give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xFF);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.
NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.
Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.
A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.
There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.
For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For 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, any two operands will result in (at most) the sum of the bits of the operands. For 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, you can estimate the maximum size of the result of a to the power of b like this:
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
(Substitute the number of bits for your target integer, of course.)
I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a 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, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).
To expand on Head Geek's answer, there is a faster way to do the addition_is_safe;
bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
L_Mask >>= 1;
L_Mask = ~L_Mask;
a &= L_Mask;
b &= L_Mask;
return ( a == 0 || b == 0 );
}
This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.
This would be even faster if you pre-initialize the mask in some constructor, since it never changes.
Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.
You could also test for the possibility of overflow before you perform the multiplication:
if ( b > ULONG_MAX / a ) // a * b would overflow
Clang 3.4+ and GCC 5+ offer checked arithmetic builtins. They offer a very fast solution to this problem, especially when compared to bit-testing safety checks.
For the example in OP's question, it would work like this:
unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// Returned non-zero: there has been an overflow
}
else
{
// Return zero: there hasn't been an overflow
}
The Clang documentation doesn't specify whether c_test contains the overflowed result if an overflow occurred, but the GCC documentation says that it does. Given that these two like to be __builtin-compatible, it's probably safe to assume that this is how Clang works too.
There is a __builtin for each arithmetic operation that can overflow (addition, subtraction, multiplication), with signed and unsigned variants, for int sizes, long sizes, and long long sizes. The syntax for the name is __builtin_[us](operation)(l?l?)_overflow:
u for unsigned or s for signed;add, sub or mul;l suffix means that the operands are ints; one l means long; two ls mean long long.So for a checked signed long integer addition, it would be __builtin_saddl_overflow. The full list can be found on the Clang documentation page.
GCC 5+ and Clang 3.8+ additionally offer generic builtins that work without specifying the type of the values: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.
The builtins lower to what's best for the platform. On x86, they check the carry, overflow and sign flags.
Visual Studio's cl.exe doesn't have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
c_in/b_in is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.
Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.
You can't access the overflow flag from C/C++.
Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.
The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.
However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.
mozilla::CheckedInt<T> provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three (IntegerTypeTraits.h, Attributes.h and Compiler.h) other header-only non-standard library headers plus Mozilla-specific assertion machinery. You probably want to replace the assertion machinery if you import the code.
Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.
You could also test for the possibility of overflow before you perform the multiplication:
if ( b > ULONG_MAX / a ) // a * b would overflow
The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.
You'll probably find that this is more efficient than doing the division as you've done in your example.
Oh, and it'll work in both C and C++ (as you've tagged the question with both).
Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:
FPE_INTOVF_TRAPInteger overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).
A bit of a shame really.
I see that a lot of people answered the question about overflow, but I wanted to address his original problem. He said the problem was to find ab=c such that all digits are used without repeating. Ok, that's not what he asked in this post, but I'm still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow (note: I'm not proficient in math so I did this step by step, but the end result was so simple that this might have a simple formula).
The main point is that the upper bound that the problem requires for either a, b or c is 98.765.432. Anyway, starting by splitting the problem in the trivial and non trivial parts:
Now we just need to show that no other solution is possible and only the permutations are valid (and then the code to print them is trivial). We go back to the upper bound. Actually the upper bound is c = 98.765.432. It's the upper bound because it's the largest number with 8 digits (10 digits total minus 1 for each a and b). This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth, as we can calculate, varying b from 2 to the upper bound:
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
Notice, for example the last line: it says that 1.97^27 ~98M. So, for example, 1^27 == 1 and 2^27 == 134.217.728 and that's not a solution because it has 9 digits (2 > 1.97 so it's actually bigger than what should be tested). As it can be seen, the combinations available for testing a and b are really small. For b == 14, we need to try 2 and 3. For b == 3, we start at 2 and stop at 462. All the results are granted to be less than ~98M.
Now just test all the combinations above and look for the ones that do not repeat any digits:
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
None of them matches the problem (which can also be seen by the absence of '0', '1', ..., '9').
The example code that solves it follows. Also note that's written in Python, not because it needs arbitrary precision integers (the code doesn't calculate anything bigger than 98 million), but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries (also note: the code has 28 lines).
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
You can't access the overflow flag from C/C++.
Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.
The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.
However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.
Here is a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of.
The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can:
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
This both ensures that if one operand is zero and one isn't, then overflow won't be falsely detected and is significantly faster than a lot of NOT/XOR/AND/test operations as previously suggested.
As pointed out, this approach, although better than other more elaborate ways, is still optimisable. The following is a revision of the original code containing the optimisation:
uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work
A more efficient and cheap way to detect multiplication overflow is:
uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
(a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;
This results in either UINT32_MAX on overflow, or the result of the multiplication. It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case.
Of note, this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows.
If using C++, you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden:
uint32_t x, y;
const bool overflow
{
[](const uint32_t x, const uint32_t y) noexcept -> bool
{
const uint32_t a{(x >> 16U) * uint16_t(y)};
const uint32_t b{uint16_t(x) * (y >> 16U)};
return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
}(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};
Here is a "non-portable" solution to the question. The Intel x86 and x64 CPUs have the so-called EFLAGS-register, which is filled in by the processor after each integer arithmetic operation. I will skip a detailed description here. The relevant flags are the "Overflow" Flag (mask 0x800) and the "Carry" Flag (mask 0x1). To interpret them correctly, one should consider if the operands are of signed or unsigned type.
Here is a practical way to check the flags from C/C++. The following code will work on Visual Studio 2005 or newer (both 32 and 64 bit), as well as on GNU C/C++ 64 bit.
#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags(const size_t query_bit_mask)
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// This code will work only on 64-bit GNU-C machines.
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags(0x801);
printf("%X\n", f);
}
If the operands were multiplied without overflow, you would get a return value of 0 from query_intel_eflags(0x801), i.e. neither the carry nor the overflow flags are set. In the provided example code of main(), an overflow occurs and the both flags are set to 1. This check does not imply any further calculations, so it should be quite fast.
I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)
With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive).
#include <limits.h>
int a = <something>;
int x = <something>;
a += x; /* UB */
if (a < 0) { /* Unreliable test */
/* ... */
}
To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:
// For addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;
// For multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.
Warning: GCC can optimize away an overflow check when compiling with -O2.
The option -Wall will give you a warning in some cases like
if (a + b < a) { /* Deal with overflow */ }
but not in this example:
b = abs(a);
if (b < 0) { /* Deal with overflow */ }
The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.
Compiling with -fwrapv solves the problem, but disables some optimizations.
We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.
There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.
For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For 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, any two operands will result in (at most) the sum of the bits of the operands. For 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, you can estimate the maximum size of the result of a to the power of b like this:
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
(Substitute the number of bits for your target integer, of course.)
I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a 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, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int mltovf(int a, int b)
{
if (a && b) return abs(a) > MAX/abs(b);
else return 0;
}
main()
{
int a, b;
for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {
if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);
}
}
For unsigned integers, just check that the result is smaller than one of the arguments:
unsigned int r, a, b;
r = a + b;
if (r < a)
{
// Overflow
}
For signed integers you can check the signs of the arguments and of the result.
Integers of different signs can't overflow, and integers of the same sign overflow only if the result is of a different sign:
signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// Overflow
}
Here is a "non-portable" solution to the question. The Intel x86 and x64 CPUs have the so-called EFLAGS-register, which is filled in by the processor after each integer arithmetic operation. I will skip a detailed description here. The relevant flags are the "Overflow" Flag (mask 0x800) and the "Carry" Flag (mask 0x1). To interpret them correctly, one should consider if the operands are of signed or unsigned type.
Here is a practical way to check the flags from C/C++. The following code will work on Visual Studio 2005 or newer (both 32 and 64 bit), as well as on GNU C/C++ 64 bit.
#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags(const size_t query_bit_mask)
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// This code will work only on 64-bit GNU-C machines.
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags(0x801);
printf("%X\n", f);
}
If the operands were multiplied without overflow, you would get a return value of 0 from query_intel_eflags(0x801), i.e. neither the carry nor the overflow flags are set. In the provided example code of main(), an overflow occurs and the both flags are set to 1. This check does not imply any further calculations, so it should be quite fast.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int mltovf(int a, int b)
{
if (a && b) return abs(a) > MAX/abs(b);
else return 0;
}
main()
{
int a, b;
for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {
if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);
}
}
To expand on Head Geek's answer, there is a faster way to do the addition_is_safe;
bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
L_Mask >>= 1;
L_Mask = ~L_Mask;
a &= L_Mask;
b &= L_Mask;
return ( a == 0 || b == 0 );
}
This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.
This would be even faster if you pre-initialize the mask in some constructor, since it never changes.
Clang now supports dynamic overflow checks for both signed and unsigned integers. See the -fsanitize=integer switch. For now, it is the only C++ compiler with fully supported dynamic overflow checking for debug purposes.
You can't access the overflow flag from C/C++.
I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.
Look at info as and info gcc.
I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)
With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive).
#include <limits.h>
int a = <something>;
int x = <something>;
a += x; /* UB */
if (a < 0) { /* Unreliable test */
/* ... */
}
To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:
// For addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;
// For multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.
Clang 3.4+ and GCC 5+ offer checked arithmetic builtins. They offer a very fast solution to this problem, especially when compared to bit-testing safety checks.
For the example in OP's question, it would work like this:
unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// Returned non-zero: there has been an overflow
}
else
{
// Return zero: there hasn't been an overflow
}
The Clang documentation doesn't specify whether c_test contains the overflowed result if an overflow occurred, but the GCC documentation says that it does. Given that these two like to be __builtin-compatible, it's probably safe to assume that this is how Clang works too.
There is a __builtin for each arithmetic operation that can overflow (addition, subtraction, multiplication), with signed and unsigned variants, for int sizes, long sizes, and long long sizes. The syntax for the name is __builtin_[us](operation)(l?l?)_overflow:
u for unsigned or s for signed;add, sub or mul;l suffix means that the operands are ints; one l means long; two ls mean long long.So for a checked signed long integer addition, it would be __builtin_saddl_overflow. The full list can be found on the Clang documentation page.
GCC 5+ and Clang 3.8+ additionally offer generic builtins that work without specifying the type of the values: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.
The builtins lower to what's best for the platform. On x86, they check the carry, overflow and sign flags.
Visual Studio's cl.exe doesn't have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
c_in/b_in is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.
Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.
It depends what you use it for. Performing unsigned long (DWORD) addition or multiplication, the best solution is to use ULARGE_INTEGER.
ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as "QuadPart" while the high DWORD is accessed as "HighPart" and the low DWORD is accessed as "LowPart".
For example:
DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
ULARGE_INTEGER a, b;
b.LowPart = Value_A; // A 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B; // A 32 bit value(up to 32 bit)
a.HighPart = 0;
a.QuadPart += b.QuadPart;
// If a.HighPart
// Then a.HighPart contains the overflow (carry)
return (a.LowPart + a.HighPart)
// Any overflow is stored in a.HighPart (up to 32 bits)
Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).
MSalter's answer is a good idea.
If the integer calculation is required (for precision), but floating point is available, you could do something like:
uint64_t foo(uint64_t a, uint64_t b) {
double dc;
dc = pow(a, b);
if (dc < UINT_MAX) {
return (powu64(a, b));
}
else {
// Overflow
}
}
I see that a lot of people answered the question about overflow, but I wanted to address his original problem. He said the problem was to find ab=c such that all digits are used without repeating. Ok, that's not what he asked in this post, but I'm still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow (note: I'm not proficient in math so I did this step by step, but the end result was so simple that this might have a simple formula).
The main point is that the upper bound that the problem requires for either a, b or c is 98.765.432. Anyway, starting by splitting the problem in the trivial and non trivial parts:
Now we just need to show that no other solution is possible and only the permutations are valid (and then the code to print them is trivial). We go back to the upper bound. Actually the upper bound is c = 98.765.432. It's the upper bound because it's the largest number with 8 digits (10 digits total minus 1 for each a and b). This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth, as we can calculate, varying b from 2 to the upper bound:
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
Notice, for example the last line: it says that 1.97^27 ~98M. So, for example, 1^27 == 1 and 2^27 == 134.217.728 and that's not a solution because it has 9 digits (2 > 1.97 so it's actually bigger than what should be tested). As it can be seen, the combinations available for testing a and b are really small. For b == 14, we need to try 2 and 3. For b == 3, we start at 2 and stop at 462. All the results are granted to be less than ~98M.
Now just test all the combinations above and look for the ones that do not repeat any digits:
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
None of them matches the problem (which can also be seen by the absence of '0', '1', ..., '9').
The example code that solves it follows. Also note that's written in Python, not because it needs arbitrary precision integers (the code doesn't calculate anything bigger than 98 million), but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries (also note: the code has 28 lines).
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.
For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For 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, any two operands will result in (at most) the sum of the bits of the operands. For 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, you can estimate the maximum size of the result of a to the power of b like this:
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
(Substitute the number of bits for your target integer, of course.)
I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a 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, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).
The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.
You'll probably find that this is more efficient than doing the division as you've done in your example.
Oh, and it'll work in both C and C++ (as you've tagged the question with both).
Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:
FPE_INTOVF_TRAPInteger overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).
A bit of a shame really.
Here is a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of.
The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can:
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
This both ensures that if one operand is zero and one isn't, then overflow won't be falsely detected and is significantly faster than a lot of NOT/XOR/AND/test operations as previously suggested.
As pointed out, this approach, although better than other more elaborate ways, is still optimisable. The following is a revision of the original code containing the optimisation:
uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work
A more efficient and cheap way to detect multiplication overflow is:
uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
(a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;
This results in either UINT32_MAX on overflow, or the result of the multiplication. It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case.
Of note, this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows.
If using C++, you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden:
uint32_t x, y;
const bool overflow
{
[](const uint32_t x, const uint32_t y) noexcept -> bool
{
const uint32_t a{(x >> 16U) * uint16_t(y)};
const uint32_t b{uint16_t(x) * (y >> 16U)};
return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
}(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};
To perform an unsigned multiplication without overflowing in a portable way the following can be used:
... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */
int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; }
if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; }
if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; }
ctZeroes -= x >> 31;
return ctZeroes;
}
Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.
Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)
#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
I defined it as a macro because otherwise the overflow bit would have been overwritten.
Subsequent is a little application with the code segement above:
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif
using namespace std;
#define detectOverflow(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
int main(int argc, char **argv) {
bool endTest = false;
bool isOverflow;
do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;
char c = 0;
do {
c = getchar();
} while ((c == '\n') && (c != EOF));
if (c == 'y' || c == 'Y') {
endTest = true;
}
do {
c = getchar();
} while ((c != '\n') && (c != EOF));
} while (!endTest);
}
MSalter's answer is a good idea.
If the integer calculation is required (for precision), but floating point is available, you could do something like:
uint64_t foo(uint64_t a, uint64_t b) {
double dc;
dc = pow(a, b);
if (dc < UINT_MAX) {
return (powu64(a, b));
}
else {
// Overflow
}
}
Clang now supports dynamic overflow checks for both signed and unsigned integers. See the -fsanitize=integer switch. For now, it is the only C++ compiler with fully supported dynamic overflow checking for debug purposes.
Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)
#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
I defined it as a macro because otherwise the overflow bit would have been overwritten.
Subsequent is a little application with the code segement above:
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif
using namespace std;
#define detectOverflow(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
int main(int argc, char **argv) {
bool endTest = false;
bool isOverflow;
do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;
char c = 0;
do {
c = getchar();
} while ((c == '\n') && (c != EOF));
if (c == 'y' || c == 'Y') {
endTest = true;
}
do {
c = getchar();
} while ((c != '\n') && (c != EOF));
} while (!endTest);
}
If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.
uint8_t x, y; /* Give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xFF);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.
NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.
A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.
For unsigned integers, just check that the result is smaller than one of the arguments:
unsigned int r, a, b;
r = a + b;
if (r < a)
{
// Overflow
}
For signed integers you can check the signs of the arguments and of the result.
Integers of different signs can't overflow, and integers of the same sign overflow only if the result is of a different sign:
signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// Overflow
}
I needed to answer this same question for floating point numbers, where bit masking and shifting does not look promising. The approach I settled on works for signed and unsigned, integer and floating point numbers. It works even if there is no larger data type to promote to for intermediate calculations. It is not the most efficient for all of these types, but because it does work for all of them, it is worth using.
Signed Overflow test, Addition and Subtraction:
Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
Compute and compare the signs of the operands.
a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.
b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.
c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.
Test for positive overflow of MAXVALUE.
a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.
b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.
Test for negative overflow of MINVALUE.
a. If both signs are negative and MINVALUE - A > B, then addition will overflow.
b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.
Otherwise, no overflow.
Signed Overflow test, Multiplication and Division:
Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)
a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.
b. If either value is one, multiplication and division cannot overflow.
c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.
d. If the magnitudes are both less than one, division cannot overflow.
Test for positive overflow of MAXVALUE.
a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.
b. If B is less than one and MAXVALUE * B < A, then division will overflow.
Otherwise, no overflow.
Note: Minimum overflow of MINVALUE is handled by 3, because we took absolute values. However, if ABS(MINVALUE) > MAXVALUE, then we will have some rare false positives.
The tests for underflow are similar, but involve EPSILON (the smallest positive number greater than zero).
Warning: GCC can optimize away an overflow check when compiling with -O2.
The option -Wall will give you a warning in some cases like
if (a + b < a) { /* Deal with overflow */ }
but not in this example:
b = abs(a);
if (b < 0) { /* Deal with overflow */ }
The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.
Compiling with -fwrapv solves the problem, but disables some optimizations.
We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.
Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.
You could also test for the possibility of overflow before you perform the multiplication:
if ( b > ULONG_MAX / a ) // a * b would overflow
Another interesting tool is IOC: An Integer Overflow Checker for C/C++.
This is a patched Clang compiler, which adds checks to the code at compile time.
You get output looking like this:
CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
You can't access the overflow flag from C/C++.
Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.
The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.
However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.
If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.
uint8_t x, y; /* Give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xFF);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.
NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.
You can't access the overflow flag from C/C++.
I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.
Look at info as and info gcc.
The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.
You'll probably find that this is more efficient than doing the division as you've done in your example.
Oh, and it'll work in both C and C++ (as you've tagged the question with both).
Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:
FPE_INTOVF_TRAPInteger overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).
A bit of a shame really.
Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.
You could also test for the possibility of overflow before you perform the multiplication:
if ( b > ULONG_MAX / a ) // a * b would overflow
It depends what you use it for. Performing unsigned long (DWORD) addition or multiplication, the best solution is to use ULARGE_INTEGER.
ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as "QuadPart" while the high DWORD is accessed as "HighPart" and the low DWORD is accessed as "LowPart".
For example:
DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
ULARGE_INTEGER a, b;
b.LowPart = Value_A; // A 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B; // A 32 bit value(up to 32 bit)
a.HighPart = 0;
a.QuadPart += b.QuadPart;
// If a.HighPart
// Then a.HighPart contains the overflow (carry)
return (a.LowPart + a.HighPart)
// Any overflow is stored in a.HighPart (up to 32 bits)
Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.
You can't access the overflow flag from C/C++.
I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.
Look at info as and info gcc.
Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.
Another variant of a solution, using assembly language, is an external procedure. This example for unsigned integer multiplication using g++ and fasm under Linux x64.
This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing).
If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8, and %r9 is used
(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.
format ELF64
section '.text' executable
public u_mul
u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret
Test:
extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);
int main() {
printf("%u\n", u_mul(4000000000,2)); // 0
printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
return 0;
}
Link the program with the asm object file. In my case, in Qt Creator, add it to LIBS in a .pro file.
To perform an unsigned multiplication without overflowing in a portable way the following can be used:
... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */
int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes += 8; value = value << 8; }
if( ( value >> 28 ) == 0 ){ ctZeroes += 4; value = value << 4; }
if( ( value >> 30 ) == 0 ){ ctZeroes += 2; value = value << 2; }
ctZeroes -= x >> 31;
return ctZeroes;
}
You can't access the overflow flag from C/C++.
Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.
The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.
However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.
If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.
uint8_t x, y; /* Give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xFF);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html
For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.
NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.
mozilla::CheckedInt<T> provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three (IntegerTypeTraits.h, Attributes.h and Compiler.h) other header-only non-standard library headers plus Mozilla-specific assertion machinery. You probably want to replace the assertion machinery if you import the code.
Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.
I needed to answer this same question for floating point numbers, where bit masking and shifting does not look promising. The approach I settled on works for signed and unsigned, integer and floating point numbers. It works even if there is no larger data type to promote to for intermediate calculations. It is not the most efficient for all of these types, but because it does work for all of them, it is worth using.
Signed Overflow test, Addition and Subtraction:
Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
Compute and compare the signs of the operands.
a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.
b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.
c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.
Test for positive overflow of MAXVALUE.
a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.
b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.
Test for negative overflow of MINVALUE.
a. If both signs are negative and MINVALUE - A > B, then addition will overflow.
b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.
Otherwise, no overflow.
Signed Overflow test, Multiplication and Division:
Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)
a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.
b. If either value is one, multiplication and division cannot overflow.
c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.
d. If the magnitudes are both less than one, division cannot overflow.
Test for positive overflow of MAXVALUE.
a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.
b. If B is less than one and MAXVALUE * B < A, then division will overflow.
Otherwise, no overflow.
Note: Minimum overflow of MINVALUE is handled by 3, because we took absolute values. However, if ABS(MINVALUE) > MAXVALUE, then we will have some rare false positives.
The tests for underflow are similar, but involve EPSILON (the smallest positive number greater than zero).
Another variant of a solution, using assembly language, is an external procedure. This example for unsigned integer multiplication using g++ and fasm under Linux x64.
This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing).
If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8, and %r9 is used
(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.
format ELF64
section '.text' executable
public u_mul
u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret
Test:
extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);
int main() {
printf("%u\n", u_mul(4000000000,2)); // 0
printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
return 0;
}
Link the program with the asm object file. In my case, in Qt Creator, add it to LIBS in a .pro file.
The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers. To use that instruction from C, one can write the following code in a 64-bit program (GCC):
unsigned long checked_imul(unsigned long a, unsigned long b) {
unsigned __int128 res = (unsigned __int128)a * b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}
For a 32-bit program, one needs to make the result 64 bit and parameters 32 bit.
An alternative is to use compiler-dependent intrinsic to check the flag register. GCC documentation for overflow intrinsic can be found from 6.56 Built-in Functions to Perform Arithmetic with Overflow Checking.
CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.
The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.
Source: Stackoverflow.com