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.co m" <ar************ ****@hotmail.co m> 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[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Peter Nilsson]

Ben Pfaff wrote:

"ar************ ****@hotmail.co m" <ar************ ****@hotmail.co m>

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.stanfor d.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.co m> 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.c om, 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.co m" <ar************ ****@hotmail.co m> 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.co m" <ar************ ****@hotmail.co m> 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.co m> 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********@com cast.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.co m> 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.c om, 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