473,322 Members | 1,314 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

sum of 64 bits using 32 bits cpu

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?
Jun 27 '08 #1
19 2740
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 ?
Jun 27 '08 #2
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
Jun 27 '08 #3
On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@usit.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 ?
Jun 27 '08 #4
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?
Jun 27 '08 #5
On 13 May, 19:17, sarahh <cohen...@gmail.comwrote:
On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@usit.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 */
}
}
}
Jun 27 '08 #6
In article <88**********************************@59g2000hsb.g ooglegroups.com>,
sarahh <co******@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
Jun 27 '08 #7
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
Jun 27 '08 #8
On May 13, 7:46 pm, Spiros Bousbouras <spi...@gmail.comwrote:
On 13 May, 19:17, sarahh <cohen...@gmail.comwrote:
On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@usit.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

Jun 27 '08 #9
On 14 מאי, 12:14, Szabolcs Borsanyi <borsa...@thphys.uni-
heidelberg.dewrote:
On May 13, 7:46 pm, Spiros Bousbouras <spi...@gmail.comwrote:


On 13 May, 19:17, sarahh <cohen...@gmail.comwrote:
On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@usit.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?
Jun 27 '08 #10
Spiros Bousbouras <sp****@gmail.comwrites:
On 13 May, 19:17, sarahh <cohen...@gmail.comwrote:
>On 13 מאי, 20:45, Hallvard B Furuseth <h.b.furus...@usit.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.
Jun 27 '08 #11
On May 14, 12:07*pm, Eligiusz Narutowicz<eligiuszdotn...@hotmail.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.
Jun 27 '08 #12
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.
Jun 27 '08 #13
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
Jun 27 '08 #14
Toms hilidhe 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
Jun 27 '08 #15
Tomás Ó hÉilidhe <to*@lavabit.comwrites:
On May 14, 12:07*pm, Eligiusz Narutowicz<eligiuszdotn...@hotmail.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 */
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.
Jun 27 '08 #16
>
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
Jun 27 '08 #17
On 14 May, 12:07, Eligiusz Narutowicz<eligiuszdotn...@hotmail.com>
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
Jun 27 '08 #18
In article <6f**********************************@k37g2000hsf. googlegroups.com>,
Bart <bc@freeuk.comwrote:
>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
Jun 27 '08 #19
rio
"Toms hilidhe" <to*@lavabit.comha scritto nel messaggio
news:24**********************************@8g2000hs e.googlegroups.com...
On May 13, 6:17 pm, sarahh <cohen...@gmail.comwrote:
>Maybe something like:
result.low = a.low + b.low;
result.high = a.high + b.high;
if (a.low & b.low & 0x8000u) ++result.high;
rerror=0; result.high=a.high; result.low=a.low;

result.low+=b.low; result.high++= b.high; rerror++=0;

if(rerror) return -1; /* error */

where "++=" operator is "add if carry"
>Again I'm not 100% sure if that's right.
I too;
it is indipendent of size for data; but sizeof(a.high)==sizeof(a.low)

Jun 27 '08 #20

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

40
by: aku | last post by:
I'm looking for the absolute fastest way to count the nr of bits that are set to "1" in a string. Presumably I then first need the fastest way to do this in a byte. I think this is it, but...
53
by: Zhiqiang Ye | last post by:
Hi, All I am reading FAQ of this group. I have a question about this: http://www.eskimo.com/~scs/C-faq/q7.31.html It says: " p = malloc(m * n); memset(p, 0, m * n); The zero fill is...
7
by: sathyashrayan | last post by:
Group, Following function will check weather a bit is set in the given variouble x. int bit_count(long x) { int n = 0; /* ** The loop will execute once for each bit of x set,
2
by: UJ | last post by:
I'm using the MS wrapper for BITS (Microsoft.MSDN.Samples.BITS) and I don't see any way to upload a file. Does anybody know of how to do that? TIA - Jeff
10
by: krunalb | last post by:
Hi, I am trying to shift unsigned long long value by 64 bits and this is what i get #include <stdio.h> int main() { unsigned short shiftby= 64;
11
by: Mack | last post by:
Hi all, I want to write a program to count number of bits set in a number. The condition is we should not loop through each bit to find whether its set or not. Thanks in advance, -Mukesh
77
by: borophyll | last post by:
As I read it, C99 states that a byte is an: "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment" (3.6) and that a byte...
6
by: John Messenger | last post by:
I notice that the C standard allows padding bits in both unsigned and signed integer types. Does anyone know of any real-world examples of compilers that use padding bits? -- John
11
by: JoeC | last post by:
I am working on a graphics program but my question has nothing to do with graphics but trying to get an algorithm to work. I set graphics from a 16x16 grid to bits of a graphic with: bitData =...
11
by: spasmous | last post by:
Just wondering.
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shllpp 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.