I need to compute recursively an integer number represented by an unsigned int down a tree.
Each node is associated with an integer value calculated recursively by multiplying the numbers of its children. The leaves have each a non-calculated static number, each being > 0.
The problem is frequent overflows. Actually, I am not interested when the result is a high number. I am OK if the result I obtain just tell me the value is > SOME_BIG_VALUE for instance (I don’t need the real value in such a case).
My idea is to use the value 0 (otherwise never used) as a convention for any “high number” and
//when multiplying a and b each being <= SOME_BIG_VALUE, there is no overflow
unsigned c = a*b;
// add a check
if (c > SOME_BIG_VALUE)
c = 0;
What is the cleanest way to define SOME_BIG_VALUE with its highest possible value for avoiding overflow ?
I consider using the definition :
#DEFINE SOME_BIG_VALUE unsigned(sqrt(UINT_MAX));
But it looks kind of dirty, isn’t it ?
I know that in most case, unsigned are represented by 32 or 64 bits but I am not sure it is guaranteed. If it is I can check in which configuration we are and create define SOME_BIG_VALUE respectively to 2^16-1 ou 2^32-1.
9
Avoiding unsigned overflow a * b
Many approaches involve finding the square root of UINT_MAX or UINT_MAX + 1.
OP’s sqrt test
This is certainly reasonable when the ((unsigned) sqrt(UINT_MAX)) is somehow coded to only evaluate once.
// Somewhat convoluted.
#define SOME_BIG_VALUE ((unsigned) sqrt(UINT_MAX))
static unsigned big_value = 0;
if (big_value == 0) {
big_value = SOME_BIG_VALUE;
}
if (a > big_value || b > big_value) {
// Potential overflow
}
A more pedantic approach could use:
#define SOME_BIG_VALUE ((unsigned) sqrt((UINT_MAX/2 + 1)*2.0) - 1) so the sqrt() is more likely exact as (UINT_MAX/2 + 1)*2.0 is a exact floating point power-of-2, the number of value bits in unsigned is very commonly even and even weak quality sqrt() get the root of even power-of-2 exactly right.
Bit width test
#define UINT_BITS (sizeof(unsigned)*CHAR_BITS)
#define SOME_BIG_VALUE ((1u << (UINT_BITS/2)) - 1)
if (a > SOME_BIG_VALUE || b > SOME_BIG_VALUE) {
// Potential overflow
}
There are ways to handle an odd sizeof(unsigned)*CHAR_BITS or unsigned with padding (see below), yet the above works for common implementations.
Bit width UINT_MAX (even if unsigned has padding):
// /a/4589384/2410359
/* Number of value bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
// Value bit width of UINT_MAX (handles padded types).
#define UINT_BITS IMAX_BITS(UINT_MAX)
C2X has UINT_WIDTH for the value-bit-width.
Run time check
if (a > 0 && b > UINT_MAX/a) {
// a * b will overflow.
}
Wider math
#if ULLONG_MAX/UINT_MAX > UINT_MAX
unsigned long long prod = a;
prod *= b;
if (prod > UINT_MAX) {
// Overflow
2
If your compiler supports an overflow-checking builtin you should use that: __builtin_umul_overflow in GCC and Clang; check the documentation for other compilers.
unsigned c;
if (__builtin_umul_overflow(a, b, &c)) {
c = 0;
}