¿Cómo detecto el desbordamiento de multiplicación de enteros sin signo?

8 minutos de lectura

¿Como detecto el desbordamiento de multiplicacion de enteros sin signo
chris johnson

Estaba escribiendo un programa en C++ para encontrar todas las soluciones de aB = Cdonde a, B y C juntos usen todos los dígitos 0-9 exactamente una vez. El programa recorrió los valores de a y By ejecutó una rutina de conteo de dígitos cada vez en a, B y aB para comprobar si se cumplió la condición de dígitos.

Sin embargo, se pueden generar soluciones espurias cuando aB sobrepasa el límite de enteros. Terminé comprobando esto usando un código como:

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

¿Hay una mejor manera de probar el desbordamiento? Sé que algunos chips tienen un indicador interno que se establece cuando se produce un desbordamiento, pero nunca he visto que se acceda a él a través de C o C++.


cuidado con eso firmado int el desbordamiento es un comportamiento indefinido en C y C++, y por lo tanto tienes que detectarlo sin causarlo realmente. Para el desbordamiento de int firmado antes de la adición, consulte Detección de desbordamiento firmado en C/C++.

  • Información que puede ser útil sobre este tema: Capítulo 5 de “Codificación segura en C y C++” de Seacord – http://www.informit.com/content/images/0321335724/samplechapter/seacord_ch05.pdf Clases SafeInt para C++ – http://blogs.msdn.com/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspxhttp://www.codeplex.com/SafeInt Biblioteca IntSafe para C: – [blogs.msdn.com/michael_howard/archiv

    – Michael Burr

    Oct 13, 2008 at 23:28

  • Seacord’s Secure Coding is a great resource, but don’t use IntegerLib. See blog.regehr.org/archives/593.

    – jww

    Sep 26, 2011 at 0:53

  • The gcc compiler option -ftrapv will cause it to generate a SIGABRT on (signed) integer overflow. See here.

    – nibot

    Oct 17, 2012 at 20:12

  • It does not answer the overflow question, but another way to come at the problem would be to use a BigNum library like GMP to guarantee you always have enough precision. You will not have to worry about overflow if you allocate enough digits up front.

    – wrdieter

    Sep 14, 2013 at 2:00

  • The information given by @HeadGeek in his answer is pretty much what I would say as well. However, with one addition. The way you are detecting overflown for a multiplication now is probably the fastest. On ARM as I’ve commented in HeadGeek’s answer you can use the clz instruction or the __clz(unsigned) function to determine the rank of the number (where its highest bit is). Since I’m unsure if this is available on x86 or x64 I will assume it is not and say that finding the most significant bit will take at worst log(sizeof(int)*8) instructions.

    – nonsensickle

    Oct 4, 2013 at 0:10

1647626767 865 ¿Como detecto el desbordamiento de multiplicacion de enteros sin signo
zneak

Starting with C23, the standard header <stdckdint.h> provides the following three function-like macros:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

where type1, type2 and type3 are any integer type. These functions respectively add, subtract or multiply a and b with arbitrary precision and store the result in *result. If the result cannot be represented exactly by type1, the function returns true (“calculation has overflowed”). (Arbitrary precision is an illusion; the calculations are very fast and almost all hardware available since the early 1990s can do it in just one or two instructions.)

Rewriting OP’s example:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

c_test contains the potentially-overflowed result of the multiplication in all cases.

Long before C23, GCC 5+ and Clang 3.8+ offer built-ins that work the same way, except that the result pointer is passed last instead of first: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+ introduced arithmetic-overflow builtins with fixed types, but they are much less flexible and Clang 3.8 has been available for a long time now. Look for __builtin_umull_overflow if you need to use this despite the more convenient newer alternative.

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.

  • __builtin_sub_overflow is definitely not in Clang 3.4.

    – Richard Cook

    Nov 3, 2015 at 17:18

  • @RichardCook, it took some time but Clang has the generic builtins as of version 3.9.

    – zneak

    Mar 26, 2016 at 2:34

  • @tambre, I don’t think there are.

    – zneak

    Mar 26, 2016 at 20:39

  • According to the docs, __builtin_add_overflow and friends should already be available on Clang 3.8.

    – Lekensteyn

    Apr 18, 2016 at 19:17

  • Thanks. This works great. Any idea what’s the corresponding function for visual c++? Can’t seem to find them.

    – Mudit Jain

    Feb 6, 2018 at 0:09

  • and of course you could rename highestOneBitPosition to log 🙂

    – Oliver Hallam

    Jan 25, 2010 at 18:14

  • Yes, it’s the same operation as log2, but that wouldn’t necessarily be as obvious to someone who didn’t have a mathematical background.

    – Head Geek

    Feb 4, 2010 at 20:19

  • Doesn’t this algorithm underestimate the safe answers? 2^31 + 0 would detect as unsafe since highestOneBitPosition(2^31) = 32. (2^32 – 1) * 1 would detect as unsafe since 32 + 1 > 32. 1 ^ 100 would detect as unsafe since 1 * 100 > 32.

    – clahey

    Apr 15, 2010 at 17:51

  • according to your multiplication_is_safe 0x8000 * 0x10000 would overflow (bit positions are 16 + 17 = 33 which is > 32), although it doesn’t because 0x8000 * 0x10000 = 0x80000000 which obviously still fits into a unsigned 32 bit int. This is just one out of may examples for which this codes does not work. 0x8000 * 0x10001, …

    – Michi

    Aug 9, 2013 at 9:46

  • This is pretty much useless. When it returns ‘safe’ – it is. Otherwise, it’s still necessary to perform the full multiplication just to be sure it really is safe. Given the potentially huge range of values that report false negatives, this has no real value, when algorithms exist to return the correct answer, without a validation step.

    – Brett Hale

    Jan 17, 2015 at 8:47


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

  • …or use numeric_limits<TYPE>::max()

    – Jonas Engström

    Oct 13, 2008 at 23:15

  • Don’t forget to handle a=0 — division breaks then.

    – Thelema

    Jul 3, 2009 at 14:24

  • @Thelema: “Don’t forget to handle a=0” – and INT_MIN / -1.

    – jww

    Jun 19, 2011 at 5:56


  • What if b == ULONG_MAX / a? Then it can still fit, given that a divides ULONG_MAX without residual.

    – the swine

    Apr 8, 2014 at 15:17

  • Funny that, performance wise, a multiplication is rather fast compared to a division and you’re adding a division for every multiplication. This doesn’t sound like the solution.

    – DrumM

    Apr 30, 2020 at 8:39


1647626767 60 ¿Como detecto el desbordamiento de multiplicacion de enteros sin signo
Peter Mortensen

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.

  • …or use numeric_limits<TYPE>::max()

    – Jonas Engström

    Oct 13, 2008 at 23:15

  • Don’t forget to handle a=0 — division breaks then.

    – Thelema

    Jul 3, 2009 at 14:24

  • @Thelema: “Don’t forget to handle a=0” – and INT_MIN / -1.

    – jww

    Jun 19, 2011 at 5:56


  • What if b == ULONG_MAX / a? Then it can still fit, given that a divides ULONG_MAX without residual.

    – the swine

    Apr 8, 2014 at 15:17

  • Funny that, performance wise, a multiplication is rather fast compared to a division and you’re adding a division for every multiplication. This doesn’t sound like the solution.

    – DrumM

    Apr 30, 2020 at 8:39


1647626767 60 ¿Como detecto el desbordamiento de multiplicacion de enteros sin signo
Peter Mortensen

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.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad