integer addition taking CARRY into account

[archilleswaterland]

Hi,

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

how do I get the carry from step one in C programming ?
Any hints ?

thanks for your time,
archilles

[Ben Pfaff]

"ar****************@hotmail.com" <ar****************@hotmail.com> writes:

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);
I am sure someone will correct me if it is wrong.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Peter Nilsson]

Ben Pfaff wrote:

"ar****************@hotmail.com" <ar****************@hotmail.com>

writes:

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);

Or...

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (a[0] > -1u - b[0]);

--
Peter

[Richard Tobin]

In article <87************@benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);

The expression for carry is unnecessarily complicated. If overflow
occurs in the first addition, c[0] will be less than *both* a[0] and
b[0], so you can compare it with either one:

c[1] = a[1] + b[1] + (c[0] < a[0]);

-- Richard

[CBFalconer]

Peter Nilsson wrote:

Ben Pfaff wrote:

<ar****************@hotmail.com> writes:

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);

Or...

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (a[0] > -1u - b[0]);

To be able to extend things limit the range to 0..INT_MAX in each
component, and then:

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + !!(c[0] & ~INT_MAX);
....
c[n] = a[n] + b[n] + !!(c[n-1] & ~INT_MAX);

Just ensure than any use of the values always masks it off with
INT_MAX. To ensure this the c[n] line should maybe become (for all
n, for n >= 1):

c[n] = a[n] + b[n] + !!(c[n-1] & ~INT_MAX);
c[n-1] = c[n-1] & INT_MAX;

The basic problem is that, while the CPU probably has a carry bit,
it is never accessible in standard C. So we have to build one
somewhere.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Joe Wright]

Ben Pfaff wrote:

"ar****************@hotmail.com" <ar****************@hotmail.com> writes:

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);
I am sure someone will correct me if it is wrong.

Good bet. if a[0] + b[0] overflows, c[0] will be less than either of
them. Only one check is necessary.

If you can get me a job out there, I'll help you with your homework. :-)
--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Eric Sosman]

Ben Pfaff wrote:

"ar****************@hotmail.com" <ar****************@hotmail.com> writes:

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);
I am sure someone will correct me if it is wrong.

Looks right to me, but I think the second line can be
simplified to

c[1] = a[1] + b[1] + (c[0] < a[0]);

That is, the two operands of the `||' will always have
the same value, so only one of them needs be tested.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Peter Nilsson]

CBFalconer wrote:

Peter Nilsson wrote:

Ben Pfaff wrote:

<ar****************@hotmail.com> writes:
I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);
Or...

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (a[0] > -1u - b[0]);

To be able to extend things limit the range to 0..INT_MAX in each
component, and then:

The sign bit is problematic. If you're going to use non-negative
int values only, then two ints will only yield 30 bits. Two
unsigned ints guarantees 32-bits.
c[0] = a[0] + b[0];
Potential undefined behaviour on int overflow!
c[1] = a[1] + b[1] + !!(c[0] & ~INT_MAX);

Obviously the OP is not using a conforming implementation, but
the question is answerable in C terms because it can be useful
to write big (or bigger) num libraries in the manner being
described here.

Keeping to ISO C topicallity, ~INT_MAX may be a trap
representation.

Coming back to unsigned types, another approach is to split
the unsigned type into two sections...

#define S 8
#define M ((1u << S) - 1)

acc = (a[0] & M) + (b[0] & M);
c[0] = acc & M;

acc = (acc >> S) + (a[0] >> S) + (b[0] >> S);
c[0] |= (acc << S);

acc /= ((-1u >> S) + 1);

c[1] = a[1] + b[1] + acc;

--
Peter

[Ben Pfaff]

Joe Wright <jo********@comcast.net> writes:

If you can get me a job out there, I'll help you with your homework. :-)

Homework? I'm a Ph.D. student. At this point in my academic
career, I assign *other* people the homework...
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[CBFalconer]

Peter Nilsson wrote:

CBFalconer wrote:

Peter Nilsson wrote:

Ben Pfaff wrote:
<ar****************@hotmail.com> writes: I am using a compiler that does not support long int (32 bits)
> so I am using 2 int's to do the work
>
> my problem
>
> int a[2];
> int b[2];
> int c[2];
>
> I want to
>
> c[0]=a[0]+b[0]; -----> Step one
> c[1]=a[1]+b[1]+carry from Step one

If unsigned integers are acceptable (replace `int' by `unsigned'
above), then I believe that the following will work:
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);

Or...

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (a[0] > -1u - b[0]);
To be able to extend things limit the range to 0..INT_MAX in each
component, and then:

The sign bit is problematic. If you're going to use non-negative
int values only, then two ints will only yield 30 bits. Two
unsigned ints guarantees 32-bits.

There is no sign bit in an unsigned int. Just think of converting
those unsigned values into registers with one less bit and one
overflow bit. That bit is the carry.

c[0] = a[0] + b[0];
Potential undefined behaviour on int overflow!

I said using unsigned above. Thus no int overflows

c[1] = a[1] + b[1] + !!(c[0] & ~INT_MAX);
Obviously the OP is not using a conforming implementation, but
the question is answerable in C terms because it can be useful
to write big (or bigger) num libraries in the manner being
described here.

Keeping to ISO C topicallity, ~INT_MAX may be a trap
representation.

Not in an unsigned int.

Coming back to unsigned types, another approach is to split
the unsigned type into two sections...

Which is what I did, except I only used one bit to hold the carry.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Peter Nilsson]

CBFalconer wrote:

Peter Nilsson wrote:

CBFalconer wrote:

Peter Nilsson wrote:
Ben Pfaff wrote:
> <ar****************@hotmail.com> writes:

>> I am using a compiler that does not support long int (32 bits)
>> so I am using 2 int's to do the work
>>
>> my problem
>>
>> int a[2];
>> int b[2];
>> int c[2];
>>
>> I want to
>>
>> c[0]=a[0]+b[0]; -----> Step one
>> c[1]=a[1]+b[1]+carry from Step one
>
> If unsigned integers are acceptable (replace `int' by `unsigned'
> above), then I believe that the following will work:
> c[0] = a[0] + b[0];
> c[1] = a[1] + b[1] + (c[0] < a[0] || c[0] < b[0]);

Or...

c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (a[0] > -1u - b[0]);

To be able to extend things limit the range to 0..INT_MAX in each
component, and then:

The sign bit is problematic. If you're going to use non-negative
int values only, then two ints will only yield 30 bits. Two
unsigned ints guarantees 32-bits.

There is no sign bit in an unsigned int.

And? The OP wanted a 32-bit range. Your limitation means the
method only uses 30 bits on a 16-bit [unsigned] int machine.
Just think of converting those unsigned values into registers
with one less bit and one overflow bit. That bit is the carry.

c[0] = a[0] + b[0];

Potential undefined behaviour on int overflow!

I said using unsigned above. Thus no int overflows

Fair enough, but...

c[1] = a[1] + b[1] + !!(c[0] & ~INT_MAX);

Obviously the OP is not using a conforming implementation, but
the question is answerable in C terms because it can be useful
to write big (or bigger) num libraries in the manner being
described here.

Keeping to ISO C topicallity, ~INT_MAX may be a trap
representation.

Not in an unsigned int.

INT_MAX has type int. The complement (~) will be performed using
signed int arithmetic.

Before you suggest ~(unsigned)INT_MAX, realise that UINT_MAX==INT_MAX
is allowed, in which case your bit mask is 0.

You could replace INT_MAX with (-1u/2), but as I said, that may mean
you don't meet the 32-bit requirement.

--
Peter

[CBFalconer]

Peter Nilsson wrote:

.... snip ...
INT_MAX has type int. The complement (~) will be performed using
signed int arithmetic.

Before you suggest ~(unsigned)INT_MAX, realise that UINT_MAX==INT_MAX
is allowed, in which case your bit mask is 0.

You could replace INT_MAX with (-1u/2), but as I said, that may mean
you don't meet the 32-bit requirement.

I don't accept this. All int bits have a weight, per standard. An
unsigned int includes the sign bit, which must have a new weight.
I don't believe UINT_MAX==INT_MAX can be consistent with the
standard.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Richard Bos]

CBFalconer <cb********@yahoo.com> wrote:

Peter Nilsson wrote:

INT_MAX has type int. The complement (~) will be performed using
signed int arithmetic.

Before you suggest ~(unsigned)INT_MAX, realise that UINT_MAX==INT_MAX
is allowed, in which case your bit mask is 0.

You could replace INT_MAX with (-1u/2), but as I said, that may mean
you don't meet the 32-bit requirement.

I don't accept this. All int bits have a weight, per standard. An
unsigned int includes the sign bit, which must have a new weight.

I can't find anything which requires that there is one more value bit in
unsigned types than in their corresponding signed type. An unsigned int
could simply have one more padding bit than a signed int.

Richard

[Peter Nilsson]

CBFalconer wrote:

Peter Nilsson wrote:

... snip ...

INT_MAX has type int. The complement (~) will be performed using
signed int arithmetic.

Before you suggest ~(unsigned)INT_MAX, realise that UINT_MAX==INT_MAX is allowed, in which case your bit mask is 0.

You could replace INT_MAX with (-1u/2), but as I said, that may mean you don't meet the 32-bit requirement.

I don't accept this. All int bits have a weight, per standard. An
unsigned int includes the sign bit, which must have a new weight.
I don't believe UINT_MAX==INT_MAX can be consistent with the
standard.

The standard is quite clear. Indeed, this has been pointed out to
you before...

6.2.6.2p1: "For unsigned integer types other than unsigned char,
the bits of the object representation shall be divided into two
groups: value bits and padding bits ..."

6.2.6.2p2: "For signed integer types, the bits of the object
representation shall be divided into three groups: value bits,
padding bits, and the sign bit. ... (if there are M value bits
in the signed type and N in the unsigned type, then M <= N).
...."

Thus, a sign bit is not a value bit, and the sign bit of a
signed integer need not contribute a value in the corresponding
unsigned type. [The only exception is unsigned char (6.2.6.1p3)]

--
Peter

[CBFalconer]

Peter Nilsson wrote:

CBFalconer wrote:
.... snip ...

I don't accept this. All int bits have a weight, per standard. An
unsigned int includes the sign bit, which must have a new weight.
I don't believe UINT_MAX==INT_MAX can be consistent with the
standard.

The standard is quite clear. Indeed, this has been pointed out to
you before...

6.2.6.2p1: "For unsigned integer types other than unsigned char,

.... snip ...
Thus, a sign bit is not a value bit, and the sign bit of a
signed integer need not contribute a value in the corresponding
unsigned type. [The only exception is unsigned char (6.2.6.1p3)]

I guess I have to concede. However I doubt that any such perverse
systems exist or have existed, apart from the DS9000. Because it
seems so unreasonable to me I will surely forget all about it again
:-[

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Lawrence Kirby]

On Wed, 06 Apr 2005 04:12:44 +0000, CBFalconer wrote:

Peter Nilsson wrote:

CBFalconer wrote: Thus, a sign bit is not a value bit, and the sign bit of a
signed integer need not contribute a value in the corresponding
unsigned type. [The only exception is unsigned char (6.2.6.1p3)]

I guess I have to concede. However I doubt that any such perverse
systems exist or have existed, apart from the DS9000. Because it
seems so unreasonable to me I will surely forget all about it again
:-[

With most hardware gravitating to 2's complement signed integer
representations these days you're probably right. But let's say you had a
1's complement or sign-magnitude based architecture that supported
integer arithmetic on just that representation, i.e. no "unsigned
compatible" arithmetic. A way to simplify the implementation of unsigned
types might be to use the signed representation but require the sign bit
to be zero. In effect it becomes a padding bit and setting it to 1 could
be considered a trap representation. It helps if the imlementation has
unusual or large register sizes because e.g. a 16 bit unsigned int has to
use all bits as value bits. And it has to do that for unsigned char
irresepctive of its size.

So I wouldn't call it unreasonable, but it is unlikely these days.

Lawrence

[Neil Kurzman]

"ar****************@hotmail.com" wrote:

Hi,

I am using a compiler that does not support long int (32 bits)
so I am using 2 int's to do the work

my problem

int a[2];
int b[2];
int c[2];

I want to

c[0]=a[0]+b[0]; -----> Step one
c[1]=a[1]+b[1]+carry from Step one

how do I get the carry from step one in C programming ?
Any hints ?

thanks for your time,
archilles

I am assuming it is an 8bit CPU. Best case you be a call to an ASM
subroutine.

What if?

you used 4 unsigned bytes but used Integer math

unsigned char A[4];
unsigned char B[4];
unsigned char C[4];
unsigned int Temp;

Temp = A[0] + B[0];
C[0] = Temp & 0xFF;

Temp = A[1] + B[1] + (Temp>>8);
C[1] = Temp & 0xFF;

and so on... with proper casts (of course) ect..