sum of 64 bits using 32 bits cpu

[sarahh]

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?

[Spiros Bousbouras]

Re: sum of 64 bits using 32 bits cpu

On 13 May, 18:17, sarahh <cohen...@gmail .comwrote:

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 ?

[Hallvard B Furuseth]

Re: sum of 64 bits using 32 bits cpu

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

[sarahh]

Re: sum of 64 bits using 32 bits cpu

On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@u sit.uio.no>
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]

Re: sum of 64 bits using 32 bits cpu

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?

[Spiros Bousbouras]

Re: sum of 64 bits using 32 bits cpu

On 13 May, 19:17, sarahh <cohen...@gmail .comwrote:

On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@u sit.uio.no>
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 */
}
}
}

[Walter Roberson]

Re: sum of 64 bits using 32 bits cpu

In article <88ed12b1-fdf8-49c8-9347-a133573276bb@59 g2000hsb.google groups.com>,
sarahh <cohen200@gmail .comwrote:

>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

[Hallvard B Furuseth]

Re: sum of 64 bits using 32 bits cpu

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

[Szabolcs Borsanyi]

Re: sum of 64 bits using 32 bits cpu

On May 13, 7:46 pm, Spiros Bousbouras <spi...@gmail.c omwrote:

On 13 May, 19:17, sarahh <cohen...@gmail .comwrote:
>
>
>

On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@u sit.uio.no>
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

[sarahh]

Re: sum of 64 bits using 32 bits cpu

On 14 מאי, 12:14, Szabolcs Borsanyi <borsa...@thphy s.uni-
heidelberg.dewr ote:

On May 13, 7:46 pm, Spiros Bousbouras <spi...@gmail.c omwrote:
>
>
>
>
>

On 13 May, 19:17, sarahh <cohen...@gmail .comwrote:

>

On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@u sit.uio.no>
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?

[Eligiusz Narutowicz]

Re: sum of 64 bits using 32 bits cpu

Spiros Bousbouras <spibou@gmail.c omwrites:

On 13 May, 19:17, sarahh <cohen...@gmail .comwrote:

>On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@u sit.uio.no>
>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.

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

Re: sum of 64 bits using 32 bits cpu

On May 14, 12:07 pm, Eligiusz Narutowicz<elig iuszdotn...@hot mail.com>
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.

[=?ISO-8859-1?Q?Tom=E1s_=D3_h=C9ilidhe?=]

Re: sum of 64 bits using 32 bits cpu

On May 13, 6:17 pm, sarahh <cohen...@gmail .comwrote:

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.

[Bart]

Re: sum of 64 bits using 32 bits cpu

On May 14, 11:47 am, sarahh <cohen...@gmail .comwrote:

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

[Hallvard B Furuseth]

Re: sum of 64 bits using 32 bits cpu

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