Integer Overflow

Discussion in 'C Programming' started by Tagore, Feb 4, 2009.

  1. Tagore

    Tagore Guest

    I want to make a function that takes two integers and checks whether
    their sum overflows or not. I have made following function for this
    purpose.
    void CheckOverflow(int a, int b)
    {
    int c=a+b;
    if((a>0)&&(b>0)&&(c<0))
    printf("Overflow");
    else
    if((a<0)&&(b<0)&&(c>0))
    printf("Overflow");
    else
    printf("Not Overflow");
    }

    It is working correctly on my compiler.
    Please check the function. Is it reliable?
    Tagore, Feb 4, 2009
    #1
    1. Advertising

  2. Tagore <> wrote:
    > I want to make a function that takes two integers
    > and checks whether their sum overflows or not.
    > I have made following function for this purpose.
    >
    > void CheckOverflow(int a, int b)
    > {
    >        int c=a+b;


    Once overflow happens, all bets are off. You need
    to check overflow _without_ generating the overflow.

    >        if((a>0)&&(b>0)&&(c<0))
    >               printf("Overflow");
    >        else
    >               if((a<0)&&(b<0)&&(c>0))
    >                     printf("Overflow");
    >               else
    >                     printf("Not Overflow");
    > }
    >
    > It is working correctly on my compiler.


    That's unlucky.

    > Please check the function. Is it reliable?


    No. Try something like...

    #include <stdio.h>
    #include <limits.h>

    void CheckOverflow(int a, int b)
    {
    if ( (a < 0 && b < INT_MIN - a)
    || (a >= 0 && b > INT_MAX - a) )
    puts("Overflow");
    else
    puts("Not Overflow");
    }

    --
    Peter
    Peter Nilsson, Feb 4, 2009
    #2
    1. Advertising

  3. Tagore

    user923005 Guest

    On Feb 4, 3:38 pm, Peter Nilsson <> wrote:
    > Tagore <> wrote:
    > > I want to make a function that takes two integers
    > > and checks whether their sum overflows or not.
    > > I have made following function for this purpose.

    >
    > > void CheckOverflow(int a, int b)
    > > {
    > >        int c=a+b;

    >
    > Once overflow happens, all bets are off. You need
    > to check overflow _without_ generating the overflow.
    >
    > >        if((a>0)&&(b>0)&&(c<0))
    > >               printf("Overflow");
    > >        else
    > >               if((a<0)&&(b<0)&&(c>0))
    > >                     printf("Overflow");
    > >               else
    > >                     printf("Not Overflow");
    > > }

    >
    > > It is working correctly on my compiler.

    >
    > That's unlucky.
    >
    > > Please check the function. Is it reliable?

    >
    > No. Try something like...
    >
    >   #include <stdio.h>
    >   #include <limits.h>
    >
    >   void CheckOverflow(int a, int b)
    >   {
    >     if (    (a <  0 && b < INT_MIN - a)
    >          || (a >= 0 && b > INT_MAX - a) )
    >       puts("Overflow");
    >     else
    >       puts("Not Overflow");
    >   }
    >
    > --
    > Peter


    If we are concerned about integer overflow, why not just choose a
    bigger type (e.g. long long).
    If long long can overflow, then we can use checks similar to those in
    your routine or choose an arbitary precision type.
    It seems to me that we have to carefully examine the sign of both
    operands so that edge cases (e.g. magnitude of LLONG_MIN can be larger
    than LLONG_MAX) and also the operation being performed (+,-,*,/,
    >>,<<).
    user923005, Feb 5, 2009
    #3
  4. Tagore

    jameskuyper Guest

    Tagore wrote:
    > I want to make a function that takes two integers and checks whether
    > their sum overflows or not. I have made following function for this
    > purpose.
    > void CheckOverflow(int a, int b)
    > {
    > int c=a+b;
    > if((a>0)&&(b>0)&&(c<0))
    > printf("Overflow");
    > else
    > if((a<0)&&(b<0)&&(c>0))
    > printf("Overflow");
    > else
    > printf("Not Overflow");
    > }
    >
    > It is working correctly on my compiler.
    > Please check the function. Is it reliable?


    Not portably. Your function relies upon the assumption that the
    program will continue to execute after the overflow, and makes some
    assumptions about what result will be stored in the variable 'c' as a
    result. The C standard doesn't say result will be stored in 'c'. It
    doesn't even guarantee that your program will continue executing after
    the overflow. It just says the behavior of your entire program is
    undefined. As a result, it's not even guaranteed that the line prior
    to "c=a+b" will be executed. As soon as it becomes inevitable that "c=a
    +b" would be executed if the other parts of the program work properly,
    the other parts of the program are no longer required to work
    properly. This sounds paradoxical, but if your code contains the line
    CheckOverflow(x,y), then the compiler is allowed to assume that x and
    y will never be given values which will cause 'c' to overflow, and to
    make optimizations based upon that assumption; optimizations that will
    cause your program to malfunction BEFORE the call to CheckOverflow, if
    that assumption is violated. That's what it means when the C standard
    says "the behavior is undefined".

    You could use a larger int type, as user923005 suggested. However, the
    C standard doesn't give you any guarantee that there is any type
    larger than int. On some machines, using 'int' expressions for this
    purpose will be faster than converting to a larger type. In any event,
    understanding how to do this without relying upon a larger type will
    allow you to do the same thing for intmax_t or long double, if you
    need to.

    Hint: no matter what values a and b have, a/2 + b/2 cannot overflow.
    That hint should point you in the right direction, but you'll have to
    think about the boundary cases carefully. The relevant code should use
    a%2, b%2, INT_MAX, and INT_MIN in various places.
    jameskuyper, Feb 5, 2009
    #4
  5. In article <>,
    Tagore <> wrote:
    >I want to make a function that takes two integers and checks whether
    >their sum overflows or not. I have made following function for this
    >purpose.


    As others have explained, you can't rely on int overflow doing
    anything in particular. If the values are non-negative, you can
    convert them to the corresponding unsigned type, and see if the sum is
    too big. If they're both negative, you can negate them and do the
    same (but bear in mind that for 2s complement the boundary case is
    different for negative and positive). If one's positive and the
    other's negative, they can't overflow.

    -- Richard
    --
    Please remember to mention me / in tapes you leave behind.
    Richard Tobin, Feb 5, 2009
    #5
  6. Tagore

    geo Guest

    On Feb 4, 6:27 pm, Tagore <> wrote:
    > I want to make a function that takes two integers and checks whether
    > their sum overflows or not. I have made following function for this
    > purpose.
    > void CheckOverflow(int a, int b)
    > {
    >        int c=a+b;
    >        if((a>0)&&(b>0)&&(c<0))
    >               printf("Overflow");
    >        else
    >               if((a<0)&&(b<0)&&(c>0))
    >                     printf("Overflow");
    >               else
    >                     printf("Not Overflow");
    >
    > }
    >
    > It is working correctly on my compiler.
    > Please check the function. Is it reliable?


    Assuming the overwhelmingly most common
    2's complement arithmetic, with
    signed int and unsigned int types,
    C makes it easy to get the overflow bit,
    via casts and the true=1, false=0 convention:

    overflow=( (unsigned int) (a+b) < (unsigned int) a );

    Some will argue that you can always get the trailing bit of
    the next longer integer type, e.g., long to long long,
    but with long long you are probably dealing with the
    longest integer type and yet the cast device will still work:

    ( (unsigned long long) (a+b) < (unsigned long long) a );

    George Marsaglia
    geo, Feb 5, 2009
    #6
  7. geo <> writes:

    > On Feb 4, 6:27 pm, Tagore <> wrote:
    >> I want to make a function that takes two integers and checks whether
    >> their sum overflows or not. I have made following function for this
    >> purpose.
    >> void CheckOverflow(int a, int b)
    >> {
    >>        int c=a+b;
    >>        if((a>0)&&(b>0)&&(c<0))
    >>               printf("Overflow");
    >>        else
    >>               if((a<0)&&(b<0)&&(c>0))
    >>                     printf("Overflow");
    >>               else
    >>                     printf("Not Overflow");
    >>
    >> }
    >>
    >> It is working correctly on my compiler.
    >> Please check the function. Is it reliable?

    >
    > Assuming the overwhelmingly most common
    > 2's complement arithmetic, with
    > signed int and unsigned int types,
    > C makes it easy to get the overflow bit,
    > via casts and the true=1, false=0 convention:
    >
    > overflow=( (unsigned int) (a+b) < (unsigned int) a );


    I am a bit baffled by this. Surely the problem case is when a and b
    are signed ints as in the OP's question? You seem to agree (why
    mention 2's complement otherwise) but I don't see how this test
    helps.

    --
    Ben.
    Ben Bacarisse, Feb 5, 2009
    #7
  8. geo <> wrote:
    > Tagore <> wrote:
    > > I want to make a function that takes two integers and
    > > checks whether their sum overflows or not. I have made
    > > following function for this purpose.
    > > void CheckOverflow(int a, int b)

    <snip>
    >
    > Assuming the overwhelmingly most common
    > 2's complement arithmetic, with
    > signed int and unsigned int types,


    2's complement is a representation, not an arithmetic.
    It does not apply to unsigned integer types. [You're
    not the first to be confused by it though.]

    > C makes it easy  to get the overflow bit,
    > via casts and the true=1, false=0 convention:
    >
    > overflow=( (unsigned int) (a+b)  < (unsigned int) a );


    You haven't avoided the overflow for signed integers.
    Even if we allow for the usual silent overflow on 2c
    machines, your test will still fail 50% of the time
    [e.g. 1 + (-1) is apparently an overflow!]

    Perhaps you're thinking of the generic wrap around test
    for unsigned types (of rank of unsigned int or higher)...

    overflow = (a + b) < a;

    --
    Peter
    Peter Nilsson, Feb 5, 2009
    #8
  9. In article <>,
    Peter Nilsson <> wrote:

    >2's complement is a representation, not an arithmetic.
    >It does not apply to unsigned integer types.


    True, but it has a special relationship to the plain unsigned binary
    representation, in that it uses exactly the same algorithms (for
    addition and subtraction). If you do unsigned arithmetic and "forget"
    that the results might be negative, you get 2s complement.

    -- Richard
    --
    Please remember to mention me / in tapes you leave behind.
    Richard Tobin, Feb 6, 2009
    #9
  10. Tagore

    CBFalconer Guest

    Richard Tobin wrote:
    > Peter Nilsson <> wrote:
    >
    >> 2's complement is a representation, not an arithmetic.
    >> It does not apply to unsigned integer types.

    >
    > True, but it has a special relationship to the plain unsigned
    > binary representation, in that it uses exactly the same algorithms
    > (for addition and subtraction). If you do unsigned arithmetic and
    > "forget" that the results might be negative, you get 2s complement.


    However, this is C, and if you do unsigned arithmetic you cannot
    get a negative result. To get a negative value you need signed
    operands, and the promotion rules will normally convert a single
    signed operand into unsigned (to agree with the other operand).

    All that means is that you are always open to the uncontrolled
    behaviour of overflowing integers, unless the system has
    appropriate provisions. If you test operands before operating, you
    have to ensure that the tests cannot involve any overflows.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Feb 7, 2009
    #10
  11. Tagore

    Curtis Dyer Guest

    On Wed, 4 Feb 2009 15:27:16 -0800 (PST),
    wrote:
    > I want to make a function that takes two integers and checks whether
    > their sum overflows or not. I have made following function for this
    > purpose.

    <snipped code>
    > It is working correctly on my compiler.
    > Please check the function. Is it reliable?


    You might find the C FAQ appropriate here:

    Q. 20.6b: <http://c-faq.com/misc/intovf.html>

    --
    Curtis
    s/sig\.invalid/gmail.com/;
    Curtis Dyer, Feb 7, 2009
    #11
  12. Tagore

    geo Guest

    On Feb 7, 2:33 am, Curtis Dyer <> wrote:
    > On Wed, 4 Feb 2009 15:27:16 -0800 (PST),
    > wrote:
    >
    > > I want to make a function that takes two integers and checks whether
    > > their sum overflows or not. I have made following function for this
    > > purpose.

    > <snipped code>
    > > It is working correctly on my compiler.
    > > Please check the function. Is it reliable?

    >
    > You might find the C FAQ appropriate here:
    >
    > Q. 20.6b:  <http://c-faq.com/misc/intovf.html>
    >
    > --
    > Curtis
    > s/sig\.invalid/gmail.com/;



    I think that particular C FAQ needs fixing or
    amplification; it certainly does not agree with
    what I, and many others---even Wikipedia---understand
    as "integer overflow".

    I summarize with details I have used in lectures for
    the past 40 years (less the last 5 after I turned 80):

    For most modern CPU's, if integers a and b are
    restricted to binary forms with k bits, then
    the carry bit is that in the (k+1) position
    should a,b and c=a+b be expressed with k+1 bits,
    even though most compilers, particularly C
    and Fortran, may cause storage and processing
    the result of c=a+b in k-bit form---in effect,
    take the result mod 2^k.

    For signed or unsigned integers, the 32-bit pattern
    produced by + or - on two integers is the same bit
    pattern that would result from doing that arithmetic
    for the modulus 2^32.
    If the integers are considered unsigned in C,
    then one is considering least-positive residues
    of the modulus 2^32, while if the integers are
    considered signed by C, and always by Fortran,
    the result may be viewed as those for
    least-absolute residues mod 2^32.

    For example, for 3-bit arithmetic mod 8,
    the positive residues are
    0,1,2,3,4,5,6,7
    while the least-absolute residues are
    0,1,2,3,-4,-3,-2,-1
    In either case, the bit patterns are
    000,001,010,011,100,101,110,111
    and for many---I think most---of us,
    overflow means that forming a,b and a+b
    to base one higher power of 2 causes
    a+b to have a leading 1 in its 4-bit
    binary representation.

    For the least-positive residue case,
    0,1,2,3,4,5,6,7 and arithmetic mod 8,
    which pairs a,b cause overflow?
    Answer:
    1+7=0,
    2+6=0,2+7=1,
    3+5=0,3+6=1,3+7=2,
    4+4=0,4+5=1,4+6=2,4+7=3,
    5+3=0,5+4=1,5+5=2,5+6=3,5+7=4
    6+2=0,6+3=1,6+4=2,6+5=3,6+6=4,6+7=5,
    7+1=0,7+2=1,7+3=2,7+4=3,7+5=4,7+6=5,7+7=6
    and such cases can be easily characterized:
    a+b < a
    which provides a simple C expression for the carry bit:
    (c<a);

    But for the least-absolute residue case, it
    is not that easy. After c=a+b, the carry bit
    is 1 for these (and only these) cases:

    1+(-1)=0,
    2+(-2)=0, 2+(-1)=1,
    3+(-3)=0, 3+(-2)=1, 3+(-1)=2,
    (-4)+(-4)=0, (-4)+(-3)=1, (-4)+(-2)=2,(-4)+(-1)=3,

    (-3)+3=0, (-3)+(-4)=1, (-3)+(-3)=2, (-3)+(-2)=3,
    (-3)+(-1)=(-4)

    (-2)+2=0, (-2)+3=1, (-2)+(-4)=2, (-2)+(-3)=3,
    (-2)+(-2)=(-4), (-2)+(-1)=(-3),

    (-1)+1=0, (-1)+2=1, (-1)+3=2, (-1)+(-4)=3,
    (-1)+(-3)=(-4), (-1)+(-2)=(-3), (-1)+(-1)=(-2)

    and characterizations are not as easy. For example,
    the carry bit is 1, that is, there is overflow if
    (and only if):

    a and b have the same sign, different from that of a+b,
    or
    a and b have opposite signs and a+b is non-negative

    Thus when a,b and c=a+b are viewed as least-absolute
    residues for arithmetic modulo a power of 2,
    that is, signed integers, then this C expression
    will provide the carry bit:

    ((a<0)==(b<0)) ? (a<0) : (a+b>=0);

    while if a,b and c=a+b are viewed merely as the
    least-positive residues for arithmetic modulo
    a power of 2, that is, unsigned integers, then
    C provides a much simpler way to get
    the carry bit resulting from c=a+b:
    (c<a);


    Can anyone provide a C version simpler than

    ((a<0)==(b<0)) ? (a<0) : (a+b>=0);

    for getting the carry bit when a,b,c are
    viewed as least-absolute residues of 2^32?

    George Marsaglia
    geo, Feb 7, 2009
    #12
  13. geo <> writes:
    > On Feb 7, 2:33 am, Curtis Dyer <> wrote:
    >> On Wed, 4 Feb 2009 15:27:16 -0800 (PST),
    >> wrote:
    >>
    >> > I want to make a function that takes two integers and checks whether
    >> > their sum overflows or not. I have made following function for this
    >> > purpose.

    >> <snipped code>
    >> > It is working correctly on my compiler.
    >> > Please check the function. Is it reliable?

    >>
    >> You might find the C FAQ appropriate here:
    >>
    >> Q. 20.6b:  <http://c-faq.com/misc/intovf.html>

    >
    > I think that particular C FAQ needs fixing or
    > amplification; it certainly does not agree with
    > what I, and many others---even Wikipedia---understand
    > as "integer overflow".


    Wikipedia doesn't define the semantics of C code. The C standard
    does.

    There is one flaw in that FAQ: it only handles positive overflow, not
    the case where the mathematical result would be less than INT_MIN.
    The "more sample code link" addresses that, but doesn't handle
    arguments with the value INT_MIN (a point that's acknowledged).

    > I summarize with details I have used in lectures for
    > the past 40 years (less the last 5 after I turned 80):

    [big snip]

    In C, the behavior for signed integer overflow is undefined. You
    cannot safely add two int values and check for overflow after the
    fact. Even if you happen to know that your CPU uses the usual
    2's-complement wraparound behavior, the compiler is allowed optimize
    based on the assumption that a computation will *not* overflow.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Feb 7, 2009
    #13
  14. Tagore

    Kaz Kylheku Guest

    On 2009-02-07, geo <> wrote:
    > I think that particular C FAQ needs fixing or
    > amplification; it certainly does not agree with
    > what I, and many others---even Wikipedia---understand
    > as "integer overflow".
    >
    > I summarize with details I have used in lectures for
    > the past 40 years (less the last 5 after I turned 80):


    Old wise man of computing! What you are saying is valid, but you have to
    distinguish the abstract language-level situation of integer overflow from the
    one that happens in CPU's.

    > For most modern CPU's, if integers a and b are
    > restricted to binary forms with k bits, then
    > the carry bit is that in the (k+1) position
    > should a,b and c=a+b be expressed with k+1 bits,
    > even though most compilers, particularly C
    > and Fortran, may cause storage and processing
    > the result of c=a+b in k-bit form---in effect,
    > take the result mod 2^k.


    Yes, this is all very well and true. On most C compilers for mainstream
    architectures, integer overflow has actual semantics like this: it wraps around
    and its effect is reversible.

    But, the fact is that in the programming language, the behavior is undefined,
    and integer overflow is simply any situation where some operation would compute
    a signed integral value that falls outside of the domain of its type (or its
    default promoted type). For example, adding two ints such that the result isn't
    in the range INT_MIN through INT_MAX.

    So as an engineer, you have to gather all these facts in order to make a
    decision whether you are going to write code that relies on the processor
    semantics of overflow, or whether you will avoid the overflow.

    As an engineer, you have to consider the tradeoffs. Here is one:

    If you depend on the machine semantics of overflow, then you cannot turn on
    overflow detection as a global code generation option for the entire project.
    This is too bad, because it could help you catch situations where overflow is
    unintended.

    You may still be able to do this on a file by file basis, depending on your
    compiler. C has no way of expressing code generation requests at the level of
    functions or expressions. Implementations may provide that as extensions, but
    typically the best you can do is control this at the invocation of a compiler
    for each translation unit.

    This thread started out with someone asking how to detect overflow. Presumably,
    he regards overflow as an error. It would be a grave mistake to implement this
    error checking in such a way that it requires you to disable any error checking
    that the compiler provides!

    If check_overflow is implemented in such a way that it triggers overflow, then
    hopefully it will be possible to turn off the overflow checks just for the
    translation unit that defines the check_oveflow, and enable it everywhere else.

    That's still an extra burden for the future maintainers who may want to port
    the program. Ideally they should just be able to turn on any option for
    catching some undefined behavior, globally for the entire codebase, and not
    have to deal with exceptions that arise.

    And what if overflow trapping is available as flag in the CPU? Then if you want
    that on a per-module basis, the generated code has to save, set and restore
    that flag everywhere. You need that in the calling conventions, i.e. the rule
    that functions must not clobber the overflow-generation flag, etc.

    > Can anyone provide a C version simpler than
    >
    > ((a<0)==(b<0)) ? (a<0) : (a+b>=0);


    But what does that have to do with overflow? Carry isn't overflow; at least
    not for the signed types that you are working with.

    Let a = b = -1. The ternary antecent is true, and hence (a < 0) is returned,
    which is 1, so there is carry. But -1 + -1 is just -2. This addition does not
    overflow.

    The carry you are talking about here is the the special unsigned signed carry
    (or borrow) for multi-precision addition (or subtraction) operations, where the
    -1 + -1 is regarded as the addition of two large unsigned numbers, and not the
    addition of one less than zero to itself!

    Why on earth would you use signed numbers in C, to detect the overflow in the
    the corresponding unsigned arithmetic???

    You're relying on the signed addition a + b to behave like unsigned addition,
    which may be true in two's complement systems, where the compiler hasn't
    generated code to implement overflow traps.

    But it takes so little effort to just use the unsigned types which are provided
    in the C language for the purpose of making this kind of computation portable!

    If U is unsigned int, then ~U gives you a portable ones-complement, and ~U+1 a
    portable twos complement, etc. Your carry check can be implemented using bit
    tests.

    The MC68000 architecture manual defines ``overflow'' (V condition code) as
    ``Set if there was an arithmetic overflow. This implies that the result is not
    representable in the operand size.'' See? A CPU architecture document still has
    the concept of a result not fitting into an operand!

    The V condition code is computed like this:

    V = Sm^Dm^Rm' v Sm'^Dm'^Rm

    Where Sm, Dm and Rm refer to the source, destination and result operands'
    most significant bits, ^ and v are AND and OR, and ' is complement (my
    notation, the manual uses a bar over the operand). So according to this we can
    do it like:

    // a + b are unsigned types; MSB_MASK and MSB_SHIFT defined sanely
    // depending on the size of the data you are representing within
    // the unsigned type.

    // overflow: 1 or 0
    (((a & b & ~(a+b)) | (~a & ~b & (a+b))) & MSB_MASK) >> MSB_SHIFT;

    There is a chance that this even runs faster than some simpler, but less
    portable, expression involving the ternary operator, because it doesn't involve
    any conditional execution. I.e. the source doesn't appear simpler, but there
    isn't necessary a performance penalty.

    Also since no ternary operator is used, in situation where a and b are
    constants, this becomes a C constant expression. Constant expressions cannot
    contain the ternary operator.

    So the above gives us a way to do an overflow check for signed addition, which
    is emulated inside unsigned types. We can also code the unsigned overflow,
    a.k.a. carry:

    C = Sm^Dm v Rm'^Dm v Sm^Rm' (MC68K architecture manual)

    i.e.

    (((a & b) | (a & ~(a+b)) | (b & ~(a+b))) ^ MSB_MASK) >> MSB_SHIFT

    A more common way in C to test whether unsigned addition overflows is to see
    whether the result fails to be greater than either operand.

    // a and b are some unsigned type that doesn't promote to a signed one

    if (a + b > a && a + b > b) {
    // didn't wrap
    }

    But this is unnecessarily strong. This weaker test is sufficient:

    if (a + b > a) {
    // didn't wrap
    }

    If b is large enough such that the addition wraps, there is no way it can wrap
    so far that the result is greater than a. The largest possible value of b can
    only wrap the result as far as a - 1. All other values of b land the result in
    the range 0 through a - 2, or else they do not overflow.

    To get the carry bit as a 0 or 1 value is simple:

    // a and b are unsigned types that do not promote to a signed type
    unsigned carry = (a + b < a);

    Contrast this with your way of doing this within the signed types:

    // a and b are (obviously) signed types
    unsigned carry = ((a<0)==(b<0)) ? (a<0) : (a+b>=0);

    This is more complicated, less portable and hostile toward maintainers who want
    to generate code that traps overflow.

    > for getting the carry bit when a,b,c are
    > viewed as least-absolute residues of 2^32?


    But from a C programming point of view, your use of the signed type is
    inconsistent with the regard for these quantities as being positive residues of
    a Mersenne number.

    The unsigned types in C are exactly for this type of purpose.
    Kaz Kylheku, Feb 8, 2009
    #14
  15. Tagore

    Boon Guest

    Keith Thompson wrote:

    > In C, the behavior for signed integer overflow is undefined. You
    > cannot safely add two int values and check for overflow after the
    > fact. Even if you happen to know that your CPU uses the usual
    > 2's-complement wraparound behavior, the compiler is allowed optimize
    > based on the assumption that a computation will *not* overflow.


    Illustration.

    $ cat overflow.c
    unsigned foo(void)
    {
    unsigned accu = 0;
    int i = 1;
    while (i > 0)
    {
    accu += i;
    ++i;
    }
    return accu;
    }

    $ gcc -O3 -S -fomit-frame-pointer overflow.c
    $ cat overflow.s
    [...]
    _foo:
    .p2align 4,,7
    L2:
    jmp L2


    i.e. gcc turns foo() into a busy loop, because it "knows" that the stop
    condition will never be true.
    Boon, Feb 10, 2009
    #15
  16. Tagore

    Tim Rentsch Guest

    Han from China <> writes:

    > CBFalconer wrote:
    > > However, this is C, and if you do unsigned arithmetic you cannot
    > > get a negative result. To get a negative value you need signed
    > > operands,

    >
    > OK.
    >
    > > and the promotion rules will normally convert a single
    > > signed operand into unsigned (to agree with the other operand).

    >
    > 6.3.1.8{1} has a separate case:
    >
    > Otherwise, if the type of the operand with signed integer type
    > can represent all of the values of the type of the operand with
    > unsigned integer type, then the operand with unsigned integer
    > type is converted to the type of the operand with signed integer
    > type.
    >
    > How do you define "normally"?


    I presume he was talking about common usage. I think it's more
    common to combine a signed type and the corresponding unsigned
    type (or one of greater precision) than it is to combine a
    signed type and an unsigned type of lesser precision. It's
    because (I conjecture) the usual arithmetic conversion rules
    favor the unsigned type for types that have the same conversion
    rank that the word "normally" was used.

    Correction for the posting being responded to: it's the usual
    arithmetic conversion rules, not the promotion rules. In cases
    where a conversion actually takes place, the promotion rules
    usually convert an unsigned type to a signed type (more
    specifically, to int).

    Editorial comment: "Value preserving" -- harrumph.
    Tim Rentsch, Feb 12, 2009
    #16
  17. Tagore

    Tim Rentsch Guest

    geo <> writes:

    > On Feb 7, 2:33 am, Curtis Dyer <> wrote:
    > > On Wed, 4 Feb 2009 15:27:16 -0800 (PST),
    > > wrote:
    > >
    > > > I want to make a function that takes two integers and checks whether
    > > > their sum overflows or not. I have made following function for this
    > > > purpose.

    > > <snipped code>
    > > > It is working correctly on my compiler.
    > > > Please check the function. Is it reliable?

    > >
    > > You might find the C FAQ appropriate here:
    > >
    > > Q. 20.6b: <http://c-faq.com/misc/intovf.html>
    > >
    > > --
    > > Curtis
    > > s/sig\.invalid/gmail.com/;

    >
    >
    > I think that particular C FAQ needs fixing or
    > amplification; it certainly does not agree with
    > what I, and many others---even Wikipedia---understand
    > as "integer overflow".
    >
    > I summarize with details I have used in lectures for
    > the past 40 years (less the last 5 after I turned 80):
    >
    > For most modern CPU's, if integers a and b are
    > restricted to binary forms with k bits, then
    > the carry bit is that in the (k+1) position
    > should a,b and c=a+b be expressed with k+1 bits,
    > even though most compilers, particularly C
    > and Fortran, may cause storage and processing
    > the result of c=a+b in k-bit form---in effect,
    > take the result mod 2^k.
    >
    > For signed or unsigned integers, the 32-bit pattern
    > produced by + or - on two integers is the same bit
    > pattern that would result from doing that arithmetic
    > for the modulus 2^32.
    > If the integers are considered unsigned in C,
    > then one is considering least-positive residues
    > of the modulus 2^32, while if the integers are
    > considered signed by C, and always by Fortran,
    > the result may be viewed as those for
    > least-absolute residues mod 2^32.
    >
    > For example, for 3-bit arithmetic mod 8,
    > the positive residues are
    > 0,1,2,3,4,5,6,7
    > while the least-absolute residues are
    > 0,1,2,3,-4,-3,-2,-1
    > In either case, the bit patterns are
    > 000,001,010,011,100,101,110,111
    > and for many---I think most---of us,
    > overflow means that forming a,b and a+b
    > to base one higher power of 2 causes
    > a+b to have a leading 1 in its 4-bit
    > binary representation.


    My experience and education don't match this usage. What you are
    calling "overflow" is what I'm used to being called "carry", or
    more exactly, the "carry" bit holds the carry value out of the
    highest bit position, considered as N-bit unsigned values. To
    avoid confusion, let's use the term "out of range" when the true
    sum cannot be represented in the representation (either signed or
    unsigned) under consideration. The term "overflow" (again, in my
    experience) describes the condition where an (N+1)-bit result,
    using sign-extended operands, differs in its two highest bit
    positions (so either 10 or 01 as the top two bits). Using this
    terminology, an unsigned sum is out of range if "carry" is
    set, and a signed sum is out of range if "overflow" is set.

    Note: I'm assuming a "canonical" representation for signed and
    unsigned integers, namely, signed represented as two's
    complement, all values legal, and unsigned having as many
    distinct values as signed (so both use exactly N bits, not
    counting any padding bits). Furthermore, comments below assume
    converting an unsigned value to a signed value of the same width
    simply reinterprets the value bits of the unsigned as a signed
    (two's complement) representation. Of course, these assumptions
    aren't valid for C in general, but they hold for a large enough
    set of implementations that they seem worth considering as a
    special case.


    > For the least-positive residue case,
    > 0,1,2,3,4,5,6,7 and arithmetic mod 8,
    > which pairs a,b cause overflow?
    > Answer:
    > 1+7=0,
    > 2+6=0,2+7=1,
    > 3+5=0,3+6=1,3+7=2,
    > 4+4=0,4+5=1,4+6=2,4+7=3,
    > 5+3=0,5+4=1,5+5=2,5+6=3,5+7=4
    > 6+2=0,6+3=1,6+4=2,6+5=3,6+6=4,6+7=5,
    > 7+1=0,7+2=1,7+3=2,7+4=3,7+5=4,7+6=5,7+7=6
    > and such cases can be easily characterized:
    > a+b < a
    > which provides a simple C expression for the carry bit:
    > (c<a);
    >
    > But for the least-absolute residue case, it
    > is not that easy. After c=a+b, the carry bit
    > is 1 for these (and only these) cases:
    >
    > 1+(-1)=0,
    > 2+(-2)=0, 2+(-1)=1,
    > 3+(-3)=0, 3+(-2)=1, 3+(-1)=2,
    > (-4)+(-4)=0, (-4)+(-3)=1, (-4)+(-2)=2,(-4)+(-1)=3,
    >
    > (-3)+3=0, (-3)+(-4)=1, (-3)+(-3)=2, (-3)+(-2)=3,
    > (-3)+(-1)=(-4)
    >
    > (-2)+2=0, (-2)+3=1, (-2)+(-4)=2, (-2)+(-3)=3,
    > (-2)+(-2)=(-4), (-2)+(-1)=(-3),
    >
    > (-1)+1=0, (-1)+2=1, (-1)+3=2, (-1)+(-4)=3,
    > (-1)+(-3)=(-4), (-1)+(-2)=(-3), (-1)+(-1)=(-2)
    >
    > and characterizations are not as easy. For example,
    > the carry bit is 1, that is, there is overflow if
    > (and only if):
    >
    > a and b have the same sign, different from that of a+b,
    > or
    > a and b have opposite signs and a+b is non-negative


    Again, this condition is what I'm used to being called "carry",
    with "overflow" used for a different condition.


    > Thus when a,b and c=a+b are viewed as least-absolute
    > residues for arithmetic modulo a power of 2,
    > that is, signed integers, then this C expression
    > will provide the carry bit:
    >
    > ((a<0)==(b<0)) ? (a<0) : (a+b>=0);
    >
    > while if a,b and c=a+b are viewed merely as the
    > least-positive residues for arithmetic modulo
    > a power of 2, that is, unsigned integers, then
    > C provides a much simpler way to get
    > the carry bit resulting from c=a+b:
    > (c<a);
    >
    >
    > Can anyone provide a C version simpler than
    >
    > ((a<0)==(b<0)) ? (a<0) : (a+b>=0);
    >
    > for getting the carry bit when a,b,c are
    > viewed as least-absolute residues of 2^32?


    Assuming we're working in a "canonical" implementation as
    described above, this condition can be evaluated by converting to
    unsigned, and then using the test for unsigned carry, e.g., for
    int a, b

    (unsigned) a + (unsigned) b < (unsigned) a

    Also, under this same assumption, a signed out-of-range condition
    can be tested by evaluating "overflow" as described above:

    /* inputs are int a, b; */
    unsigned ua = a, ub = b;
    unsigned usum = ua + ub;
    unsigned overflow = (usum ^ ua ^ ub)>>(N-1) ^ (usum < ua);
    if( overflow ){ /* a+b is out of range */ }
    else {
    /* In "canonical" implementations, the assertion below works. */
    assert( a + b == (int) usum );
    }

    Here N represents the width of unsigned (and also signed) ints.

    Reviewing the conditions:

    INT_MIN + 1 == -INT_MAX
    UINT_MAX > INT_MAX
    UINT_MAX + INT_MIN == INT_MAX
    N == number of value bits in an unsigned int
    Converting unsigned to signed just reinterprets the bits of
    the unsigned as their signed counterparts, in particular
    including the sign bit
    Tim Rentsch, Feb 13, 2009
    #17
  18. On 13 Feb 2009 09:11:55 -0800, Tim Rentsch <>
    wrote:


    snip

    >My experience and education don't match this usage. What you are
    >calling "overflow" is what I'm used to being called "carry", or
    >more exactly, the "carry" bit holds the carry value out of the
    >highest bit position, considered as N-bit unsigned values. To
    >avoid confusion, let's use the term "out of range" when the true
    >sum cannot be represented in the representation (either signed or
    >unsigned) under consideration. The term "overflow" (again, in my
    >experience) describes the condition where an (N+1)-bit result,
    >using sign-extended operands, differs in its two highest bit
    >positions (so either 10 or 01 as the top two bits). Using this
    >terminology, an unsigned sum is out of range if "carry" is
    >set, and a signed sum is out of range if "overflow" is set.


    Except that my system doesn't have any carry bits at all and the
    standard uses the term "integer overflow".

    --
    Remove del for email
    Barry Schwarz, Feb 14, 2009
    #18
  19. Tagore

    Tim Rentsch Guest

    Barry Schwarz <> writes:

    > On 13 Feb 2009 09:11:55 -0800, Tim Rentsch <>
    > wrote:
    >
    >
    > snip
    >
    > >My experience and education don't match this usage. What you are
    > >calling "overflow" is what I'm used to being called "carry", or
    > >more exactly, the "carry" bit holds the carry value out of the
    > >highest bit position, considered as N-bit unsigned values. To
    > >avoid confusion, let's use the term "out of range" when the true
    > >sum cannot be represented in the representation (either signed or
    > >unsigned) under consideration. The term "overflow" (again, in my
    > >experience) describes the condition where an (N+1)-bit result,
    > >using sign-extended operands, differs in its two highest bit
    > >positions (so either 10 or 01 as the top two bits). Using this
    > >terminology, an unsigned sum is out of range if "carry" is
    > >set, and a signed sum is out of range if "overflow" is set.

    >
    > Except that my system doesn't have any carry bits at all and the
    > standard uses the term "integer overflow".


    As should have been obvious, this terminology was providing
    context for an answer to a C question.
    Tim Rentsch, Feb 14, 2009
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. bartek
    Replies:
    3
    Views:
    3,084
    bartek
    Feb 6, 2004
  2. John Black
    Replies:
    1
    Views:
    4,494
    John Harrison
    Apr 15, 2004
  3. deancoo

    integer or long overflow...

    deancoo, Mar 5, 2005, in forum: C++
    Replies:
    11
    Views:
    752
    Pete Becker
    Mar 5, 2005
  4. Enrico 'Trippo' Porreca

    Integer overflow

    Enrico 'Trippo' Porreca, Aug 21, 2003, in forum: C Programming
    Replies:
    9
    Views:
    406
  5. Ashutosh Iddya

    integer overflow

    Ashutosh Iddya, Apr 16, 2004, in forum: C Programming
    Replies:
    25
    Views:
    914
    RoSsIaCrIiLoIA
    Apr 24, 2004
Loading...

Share This Page