sum of 64 bits using 32 bits cpu

Discussion in 'C Programming' started by sarahh, May 13, 2008.

  1. sarahh

    sarahh Guest

    Hi, I need help in the following question .
    I have a cpu that knows to do the computations on 32 bits(unsigned
    integer(
    write a function that gets 2 64 bits numbers and return their sum.
    I start with the following structure.

    typedef struct{
    unsigned int low;
    unsigned int high;
    }64bits;

    and define the nums
    64bits num1.num2;

    1.I know that the limit of unsigned integer is ~64000 what happend in
    case of overflow it start again from 0.?

    2.could someone add solution for the question?
    sarahh, May 13, 2008
    #1
    1. Advertising

  2. On 13 May, 18:17, sarahh <> wrote:
    > Hi, I need help in the following question .
    > I have a cpu that knows to do the computations on 32 bits(unsigned
    > integer(
    > write a function that gets 2 64 bits numbers and return their sum.
    > I start with the following structure.
    >
    > typedef struct{
    > unsigned int low;
    > unsigned int high;
    >
    > }64bits;
    >
    > and define the nums
    > 64bits num1.num2;


    Are you working on a C89 compiler which
    means you don't have unsigned long long
    available ?

    > 1.I know that the limit of unsigned integer is ~64000 what happend in
    > case of overflow it start again from 0.?


    UINT_MAX is guaranteed to be at least 65535. It could
    be a lot more , in fact the standard doesn't specify an
    upper bound. And yes it will wrap around upon reaching
    UINT_MAX + 1

    > 2.could someone add solution for the question?


    Is it homework ?
    Spiros Bousbouras, May 13, 2008
    #2
    1. Advertising

  3. sarahh writes:
    > 1.I know that the limit of unsigned integer is ~64000


    ....on a host where unsigned int is 32-bit like on your question, yes....

    > what happend in case of overflow it start again from 0.?


    Yes. With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0.
    Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.

    (Strictly speaking this is not what is called overflow in the C language
    - precisely because it is well-defined. "overflow" is what happens to
    signed integers, where the result is not defined.)

    > 2.could someone add solution for the question?


    The point of homework is to learn by doing. But if you need a hint:
    Think of how you do addition of two-digit numbers by hand, and think
    of low and high as the two digits of a number. (In base 0x100000000
    instead of base 10, but what the hey...) You need to check somehow
    whether there was carry from adding the "low" digits.

    --
    Hallvard
    Hallvard B Furuseth, May 13, 2008
    #3
  4. sarahh

    sarahh Guest

    On 13 מ××™, 20:45, Hallvard B Furuseth <>
    wrote:
    > sarahh writes:
    > > 1.I know that the limit of unsigned integer is ~64000

    >
    > ...on a host where unsigned int is 32-bit like on your question, yes....
    >
    > > what happend in case of overflow it start again from 0.?

    >
    > Yes. With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0..
    > Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.
    >
    > (Strictly speaking this is not what is called overflow in the C language
    > - precisely because it is well-defined. "overflow" is what happens to
    > signed integers, where the result is not defined.)
    >
    > > 2.could someone add solution for the question?

    >
    > The point of homework is to learn by doing. But if you need a hint:
    > Think of how you do addition of two-digit numbers by hand, and think
    > of low and high as the two digits of a number. (In base 0x100000000
    > instead of base 10, but what the hey...) You need to check somehow
    > whether there was carry from adding the "low" digits.
    >
    > --
    > Hallvard


    Thanks,know I understand it better what about not unsigned, what
    happend if I add to max+1 ?
    sarahh, May 13, 2008
    #4
  5. sarahh

    sarahh Guest

    It is not homework it is a question from interview I did .*****

    just to be sure about unsigned int
    I know that in base 10 it is
    ~65,000
    when I add it 1 ,I return to 0.
    I don't understand it because I write it in c and I get number bigger
    than the limit.
    what I lost?
    sarahh, May 13, 2008
    #5
  6. On 13 May, 19:17, sarahh <> wrote:
    > On 13 מ××™, 20:45, Hallvard B Furuseth <>
    > wrote:
    >
    > > sarahh writes:
    > > > 1.I know that the limit of unsigned integer is ~64000

    >
    > > ...on a host where unsigned int is 32-bit like on your question, yes....

    >
    > > > what happend in case of overflow it start again from 0.?

    >
    > > Yes. With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0.
    > > Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.

    >
    > > (Strictly speaking this is not what is called overflow in the C language
    > > - precisely because it is well-defined. "overflow" is what happens to
    > > signed integers, where the result is not defined.)

    >
    > > > 2.could someone add solution for the question?

    >
    > > The point of homework is to learn by doing. But if you need a hint:
    > > Think of how you do addition of two-digit numbers by hand, and think
    > > of low and high as the two digits of a number. (In base 0x100000000
    > > instead of base 10, but what the hey...) You need to check somehow
    > > whether there was carry from adding the "low" digits.
    > >

    > Thanks,know I understand it better what about not unsigned, what
    > happend if I add to max+1 ?


    Undefined behaviour. Hallvard Furuseth has said
    so already. Undefined behaviour has as an implication
    that you cannot predict the outcome so you must
    not allow undefined behaviour to appear in your code.
    In other words, when you are dealing with signed
    integers you must either know that the values your
    programme will be dealing with will be such that no
    overflow will occur or you need to check *before*
    performing the arithmetic operations whether they
    will lead to overflow and if yes take appropriate measures
    like emit an error message or something.

    Example:

    #include <limits.h>
    /* ..... */
    int a,b,c ;
    /* ..... */
    /* We want to perform c = a+b without risking
    * undefined behaviour.
    */
    if ( a >= 0 ) {
    if ( b >= 0 ) {
    if ( a <= INT_MAX - b ) {
    c = a+b ;
    } else {
    /* OVERFLOW */
    }
    } else {
    c = a+b ;
    }
    } else {
    if ( b >= 0 ) {
    c = a+b ;
    } else {
    if ( a >= INT_MIN - b ) {
    c = a+b ;
    } else {
    /* OVERFLOW */
    }
    }
    }
    Spiros Bousbouras, May 13, 2008
    #6
  7. In article <>,
    sarahh <> wrote:

    >just to be sure about unsigned int
    > I know that in base 10 it is
    >~65,000
    >when I add it 1 ,I return to 0.
    >I don't understand it because I write it in c and I get number bigger
    >than the limit.
    >what I lost?


    The maximum unsigned int is only 65535 on systems using 16 bit
    integers. if the system you were using had 32 bit integers, then
    you would have gotten different results than you expected,
    depending exactly how you wrote the constants and exactly which
    format you used to print them out.
    --
    "When we all think alike no one is thinking very much."
    -- Walter Lippmann
    Walter Roberson, May 13, 2008
    #7
  8. Walter Roberson writes:
    > The maximum unsigned int is only 65535 on systems using 16 bit
    > integers. if the system you were using had 32 bit integers, (...)


    duh, I was reading too quicly to notice that...

    --
    Hallvard
    Hallvard B Furuseth, May 13, 2008
    #8
  9. On May 13, 7:46 pm, Spiros Bousbouras <> wrote:
    > On 13 May, 19:17, sarahh <> wrote:
    >
    >
    >
    > > On 13 מ××™, 20:45, Hallvard B Furuseth <>
    > > wrote:

    >
    > > > sarahh writes:
    > > > > 1.I know that the limit of unsigned integer is ~64000

    >
    > > > ...on a host where unsigned int is 32-bit like on your question, yes.....

    >
    > > > > what happend in case of overflow it start again from 0.?

    >
    > > > Yes. With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0.
    > > > Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.

    >
    > > > (Strictly speaking this is not what is called overflow in the C language
    > > > - precisely because it is well-defined. "overflow" is what happens to
    > > > signed integers, where the result is not defined.)

    >
    > > Thanks,know I understand it better what about not unsigned, what
    > > happend if I add to max+1 ?

    >
    > Undefined behaviour. Hallvard Furuseth has said


    I think the OP was interested in unsigned numbers, where there is no
    undefined behaviour (UB) nor implementation defined behaviour (IDB)
    For signed numbers: overflow is UB.
    But it is IDB whether or not the signed numbers are represented as
    two's-compement. And it is well defined how to convert a signed number
    to unsigned, and how to add them. Then it is IDB how to convert them
    back
    to a signed integer. So
    int a,b;
    (int)((unsigned)a+b) has IDB
    but a+b has UB
    on overflow.
    If the OP's system represents negative numbers as two's complement, he
    may
    well stick to unsigned arithmetics, as it will just reproduce what he
    wants,
    even with signed numbers.

    Szabolcs
    Szabolcs Borsanyi, May 14, 2008
    #9
  10. sarahh

    sarahh Guest

    On 14 מ××™, 12:14, Szabolcs Borsanyi <-
    heidelberg.de> wrote:
    > On May 13, 7:46 pm, Spiros Bousbouras <> wrote:
    >
    >
    >
    >
    >
    > > On 13 May, 19:17, sarahh <> wrote:

    >
    > > > On 13 מ××™, 20:45, Hallvard B Furuseth <>
    > > > wrote:

    >
    > > > > sarahh writes:
    > > > > > 1.I know that the limit of unsigned integer is ~64000

    >
    > > > > ...on a host where unsigned int is 32-bit like on your question, yes.....

    >
    > > > > > what happend in case of overflow it start again from 0.?

    >
    > > > > Yes.  With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0.
    > > > > Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.

    >
    > > > > (Strictly speaking this is not what is called overflow in the C language
    > > > > - precisely because it is well-defined.  "overflow" is what happens to
    > > > > signed integers, where the result is not defined.)

    >
    > > > Thanks,know I understand it better what about not unsigned, what
    > > > happend if I add to max+1 ?

    >
    > > Undefined behaviour. Hallvard Furuseth has said

    >
    > I think the OP was interested in unsigned numbers, where there is no
    > undefined behaviour (UB) nor implementation defined behaviour (IDB)
    > For signed numbers: overflow is UB.
    > But it is IDB whether or not the signed numbers are represented as
    > two's-compement. And it is well defined how to convert a signed number
    > to unsigned, and how to add them. Then it is IDB how to convert them
    > back
    > to a signed integer. So
    > int a,b;
    > (int)((unsigned)a+b) has IDB
    > but a+b has UB
    > on overflow.
    > If the OP's system represents negative numbers as two's complement, he
    > may
    > well stick to unsigned arithmetics, as it will just reproduce what he
    > wants,
    > even with signed numbers.
    >
    > Szabolcs-הסתר טקסט מצוטט-
    >
    > -הר××” טקסט מצוטט-


    So,how should I recognize overflow in adding two unsigned nums?
    sarahh, May 14, 2008
    #10
  11. Spiros Bousbouras <> writes:

    > On 13 May, 19:17, sarahh <> wrote:
    >> On 13 מ××™, 20:45, Hallvard B Furuseth <>
    >> wrote:
    >>
    >> > sarahh writes:
    >> > > 1.I know that the limit of unsigned integer is ~64000

    >>
    >> > ...on a host where unsigned int is 32-bit like on your question, yes....

    >>
    >> > > what happend in case of overflow it start again from 0.?

    >>
    >> > Yes. With 32-bit unsigned int, 0xffffffffU (all bits = 1) + 1U == 0.
    >> > Unsigned arithmetic is defined as modulo-(max value + 1) arithmetic.

    >>
    >> > (Strictly speaking this is not what is called overflow in the C language
    >> > - precisely because it is well-defined. "overflow" is what happens to
    >> > signed integers, where the result is not defined.)

    >>
    >> > > 2.could someone add solution for the question?

    >>
    >> > The point of homework is to learn by doing. But if you need a hint:
    >> > Think of how you do addition of two-digit numbers by hand, and think
    >> > of low and high as the two digits of a number. (In base 0x100000000
    >> > instead of base 10, but what the hey...) You need to check somehow
    >> > whether there was carry from adding the "low" digits.
    >> >

    >> Thanks,know I understand it better what about not unsigned, what
    >> happend if I add to max+1 ?

    >
    > Undefined behaviour. Hallvard Furuseth has said
    > so already. Undefined behaviour has as an implication
    > that you cannot predict the outcome so you must
    > not allow undefined behaviour to appear in your code.
    > In other words, when you are dealing with signed
    > integers you must either know that the values your
    > programme will be dealing with will be such that no
    > overflow will occur or you need to check *before*
    > performing the arithmetic operations whether they
    > will lead to overflow and if yes take appropriate measures
    > like emit an error message or something.
    >
    > Example:
    >
    > #include <limits.h>
    > /* ..... */
    > int a,b,c ;
    > /* ..... */
    > /* We want to perform c = a+b without risking
    > * undefined behaviour.
    > */
    > if ( a >= 0 ) {
    > if ( b >= 0 ) {
    > if ( a <= INT_MAX - b ) {
    > c = a+b ;
    > } else {
    > /* OVERFLOW */
    > }
    > } else {
    > c = a+b ;
    > }
    > } else {
    > if ( b >= 0 ) {
    > c = a+b ;
    > } else {
    > if ( a >= INT_MIN - b ) {
    > c = a+b ;
    > } else {
    > /* OVERFLOW */
    > }
    > }
    > }


    I often wonder about this nonsensical part of the standard.
    Eligiusz Narutowicz, May 14, 2008
    #11
  12. On May 14, 12:07 pm, Eligiusz Narutowicz<>
    wrote:

    > I often wonder about this nonsensical part of the standard.



    Are you referring to the overflow of signed integers having undefined
    behaviour? If so:

    The reason for this, I think, is that there are many processors that
    have a "STATUS" register which uses bits to store such info as:
    * The result of the last arithmetic operation was 0.
    * The last arithmetic operation overflowed.

    If you had:

    int i = 7;

    i -= 34;

    /* Now the STATUS register says there was overflow */

    if (i) DoSomething();

    When the compiler sees "if (i)", it will simply check the STATUS
    register to see if the last operation resulted in zero. If an unsigned
    type is involved, then it's possible to have overflow and zero at the
    same time. With signed however, it doesn't bother checking for
    overflow, it just checks for zero. This is unreliable for some reason.
    Something along those lines in anyway.

    Somebody posted a nice anecdote about how people were complaining to a
    compiler manufacturer about getting dodgy behaviour out of "if (i)"
    after an overflow occurred, but the compiler writer was in strict
    abidance of the C89 Standard.
    Tomás Ó hÉilidhe, May 14, 2008
    #12
  13. On May 13, 6:17 pm, sarahh <> wrote:
    > Hi, I need help in the following question .
    > I have a cpu that knows to do the computations on 32 bits(unsigned
    > integer(
    > write a function that gets 2 64 bits numbers and return their sum.
    > I start with the following structure.
    >
    > typedef struct{
    > unsigned int low;
    > unsigned int high;
    >
    > }64bits;



    This is more of a computer science/mathematical question that a C
    question.

    Anyhow if you want to add these two numbers, here's what you need to
    do:

    1) Add the least significant 16 bits together:

    result.low = a.low + b.low

    2) Then add the most significant 16 bits together:

    result.high = a.high + b.high

    3) Now, if the addition of the lower parts resulted in an overflow,
    then you must add 1 to the higher part. (I'm not 100% sure by the way,
    I only thought about it for a few seconds).

    Maybe something like:

    result.low = a.low + b.low;
    result.high = a.high + b.high;
    if (a.low & b.low & 0x8000u) ++result.high;

    Again I'm not 100% sure if that's right.

    Disclaimer: Unsigned integers aren't guaranteed to be 16-Bit by any C
    standard.
    Tomás Ó hÉilidhe, May 14, 2008
    #13
  14. sarahh

    Bart Guest

    On May 14, 11:47 am, sarahh <> wrote:

    > So,how should I recognize overflow in adding two unsigned nums?- Hide quoted text -


    Try this (translated into C):

    C = A+B;

    if C<A or C<B then Overflow.

    (Don't know if it's foolproof but it did work with one combination of
    A,B, so...)

    --
    Bartc
    Bart, May 14, 2008
    #14
  15. Tomás Ó hÉilidhe writes:
    > Maybe something like:
    > result.low = a.low + b.low;
    > result.high = a.high + b.high;
    > if (a.low & b.low & 0x8000u) ++result.high;
    > Again I'm not 100% sure if that's right.


    Wrong for 0xFFFF + 1 (given 16-bit).

    One possible test: Do the same as with signed int: check if
    UINT_MAX - a.low > b.low
    which means the add would overflow. Another:
    result.low = a.low + b.low;
    if (result.low < a.low) it wrapped around;

    > Disclaimer: Unsigned integers aren't guaranteed to be 16-Bit by any C
    > standard.


    In particular not since he has 32-bit integers:)

    --
    Hallvard
    Hallvard B Furuseth, May 14, 2008
    #15
  16. Tomás Ó hÉilidhe <> writes:

    > On May 14, 12:07 pm, Eligiusz Narutowicz<>
    > wrote:
    >
    >> I often wonder about this nonsensical part of the standard.

    >
    >
    > Are you referring to the overflow of signed integers having undefined
    > behaviour? If so:
    >
    > The reason for this, I think, is that there are many processors that
    > have a "STATUS" register which uses bits to store such info as:
    > * The result of the last arithmetic operation was 0.
    > * The last arithmetic operation overflowed.
    >
    > If you had:
    >
    > int i = 7;
    >
    > i -= 34;
    >
    > /* Now the STATUS register says there was overflow */


    This was probably not the xample you intended as there is no overflow.

    >
    > if (i) DoSomething();
    >
    > When the compiler sees "if (i)", it will simply check the STATUS
    > register to see if the last operation resulted in zero. If an unsigned
    > type is involved, then it's possible to have overflow and zero at the
    > same time. With signed however, it doesn't bother checking for
    > overflow, it just checks for zero. This is unreliable for some reason.
    > Something along those lines in anyway.
    >
    > Somebody posted a nice anecdote about how people were complaining to a
    > compiler manufacturer about getting dodgy behaviour out of "if (i)"
    > after an overflow occurred, but the compiler writer was in strict
    > abidance of the C89 Standard.
    Eligiusz Narutowicz, May 14, 2008
    #16
  17. >
    > One possible test: Do the same as with signed int: check if
    > UINT_MAX - a.low > b.low

    This should work, indeed.
    This is the downside of C as a high level assembler.
    implementing multiplication and addition of wide integers is quite
    straigthforward in (e.g x86-)assembly, whereas in C
    there is not even an implementation defined behaviour that could yield
    access to a carry flag, an ADC instruction, or the feature of MUL that
    gives
    an integer of double width.

    Still, I guess, one can still avoid the expensive conditionals.
    Keeping
    integers in the lower half of the builtin type, there is a char access
    to
    the carry flag. Then one needs seven additions for a 64bit type.
    (Endianness
    has to be known)
    I made no measurements on efficiency. (If efficiency is important, one
    clearly relaxes C for this problem.)

    Szabolcs
    Szabolcs Borsanyi, May 14, 2008
    #17
  18. On 14 May, 12:07, Eligiusz Narutowicz<>
    wrote:
    > I often wonder about this nonsensical part of the standard.


    If you mean the fact that exceeding the bounds in
    signed arithmetic has undefined consequences then
    I believe the answer is that different architectures
    behave in a different manner. I have heard of the
    following behaviours:

    1) Wraparound.
    2) If the overflow is towards the maximum value then
    the result is the maximum value. Some DSPs exhibit
    this behaviour.
    3) Generation of a signal specific to the implementation.

    There may be more behaviours. The following thread may
    also be of interest
    http://tinyurl.com/4r3zum
    Spiros Bousbouras, May 14, 2008
    #18
  19. In article <>,
    Bart <> wrote:

    >C = A+B;
    >
    >if C<A or C<B then Overflow.


    You only need to test either one of these.

    >(Don't know if it's foolproof but it did work with one combination of
    >A,B, so...)


    Not a very thorough test!

    It's easy to see that it's true. If there isn't overflow, obviously
    A+B >= A and A+B >= B. If it does overflow, then even if B is
    the maximum value for this unsigned type the result will only be
    A-1, so A+B < A and likewise for B.

    (You have to be careful that the result is unsigned, as noted in
    several threads recently. It will be if A and B are unsigned
    int, but probablyh not if they are unsigned short.)

    -- Richard
    --
    :wq
    Richard Tobin, May 14, 2008
    #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. GGG
    Replies:
    10
    Views:
    12,511
    Donar
    Jul 6, 2006
  2. sarmin kho
    Replies:
    2
    Views:
    816
    A. Lloyd Flanagan
    Jun 15, 2004
  3. Miki Tebeka
    Replies:
    1
    Views:
    432
    Marcin 'Qrczak' Kowalczyk
    Jun 14, 2004
  4. Replies:
    6
    Views:
    366
    Alf P. Steinbach
    Sep 25, 2007
  5. pavunkumar

    How , system cpu and user cpu times calculates

    pavunkumar, Feb 27, 2009, in forum: C Programming
    Replies:
    1
    Views:
    337
Loading...

Share This Page