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

9 minutos de lectura

avatar de usuario
chris johnson

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

Sin embargo, se pueden generar soluciones espurias cuando unb 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

user avatar
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

user avatar
Tyler Durden

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;
}

  • Unsigned integers don’t strictly overflow in C++ either (ISO/IEC 14882:2003 3.9.1.4). My use of ‘overflow’ in the question was the more colloquial meaning, intended to include the well-defined wrapping of unsigned types, since I was interested in unsigned ints representing mathematical positive integers, not positive integers mod 2^32 (or 2^64). The distinction between overflow as a deviation from mathematical infinite-sized integer behaviour, and overflow as an undefined behaviour in the language seems rarely to be made explicit.

    – Chris Johnson

    Oct 3, 2009 at 18:47

  • That test doesn’t need to be x >= 0x > 0 will suffice (if x == 0, then x + a can’t overflow for obvious reasons).

    – caf

    Apr 26, 2010 at 0:20

  • @pmg, is there a supporting quote from the standard?

    – Pacerier

    Sep 22, 2013 at 17:39


  • I like this approach… However, be careful: the multiplication overflow detection assumes a posiive x. For x == 0, it leads to divide by zero detection, and for negative x, it always erroneously detects overflow.

    – Franz D.

    Nov 16, 2016 at 16:31

  • if ((a < INT_MIN / x)) test is too late. A if (x == -1) test is needed first.

    – chux – Reinstate Monica

    Jan 11, 2017 at 19:11


user avatar
Peter Mortensen

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)

user avatar
Peter Mortensen

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.

  • Doesn’t this invoke undefined behavior? Signed overflow is undefined behavior. Correct me if I’m wrong, but even if you don’t use the result, you get UB. stackoverflow.com/questions/16188263/…

    – PersonWithName

    Jul 1, 2021 at 7:38

  • You might have to do the multiplication in assembly too if you want to avoid UB.

    – PersonWithName

    Jul 1, 2021 at 7:39

¿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