Discussion in 'C Programming' started by mohangupta13, Dec 14, 2009.

1. ### mohangupta13Guest

Hello all , I just came across an interesting question .
Q. Add two numbers using bit operations in C?

I came up with the below solution .Though it does work , But I believe
there must be a better way to solve this question . Please provide

int a_bit=0,b_bit=0;
for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
sum=a_bit+b_bit+carry;
switch(sum){
case 0: carry=0;//this bit in c is already 0
break;
case 1: //make this bit in c 1
carry=0;
break;
case 2: //make this bit zero and carry=1
carry=1;
break;
case 3: //make this bit 1 and carry =1
carry=1;
break;
default: printf("this must not have happened \n");
return -1;
}
}
return c;
}

And one more thing does the C standard specify that for an integral
number the MSB is a sign bit or does it say something about the bit
representation of types??

Thanks
Mohan Gupta

mohangupta13, Dec 14, 2009

2. ### Tom St DenisGuest

On Dec 14, 8:12 am, mohangupta13 <> wrote:
> Hello all , I just came across an interesting question .
> Q. Add two numbers using bit operations in C?
>
> I came up with the below solution .Though it does work , But I believe
> there must be a better way to solve this question . Please provide
>
>
> int a_bit=0,b_bit=0;
> for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
>         sum=a_bit+b_bit+carry;
>         switch(sum){
>                 case 0: carry=0;//this bit in c is already 0
>                         break;
>                 case 1: //make this bit in c 1
>                         carry=0;
>                         break;
>                 case 2: //make this bit zero and carry=1
>                         //this bit is already zero
>                         carry=1;
>                         break;
>                 case 3: //make this bit 1 and carry =1
>                         carry=1;
>                         break;
>                 default: printf("this must not have happened \n");
>                          return -1;
>                 }
>
> }
> return c;
> }
>
> And one more thing does the C standard specify that for an integral
> number the MSB is a sign bit or does it say something  about the bit
> representation of types??

You want to do some variant of

sum = a ^ b ^ carry
carry[i+1] = (a & carry) | (b & carry) | (a & b)

Tom

Tom St Denis, Dec 14, 2009

3. ### mohangupta13Guest

On Dec 14, 6:34 pm, Tom St Denis <> wrote:
> On Dec 14, 8:12 am, mohangupta13 <> wrote:
>
>
>
> > Hello all , I just came across an interesting question .
> > Q. Add two numbers using bit operations in C?

>
> > I came up with the below solution .Though it does work , But I believe
> > there must be a better way to solve this question . Please provide

>
> > int add(int a,int b){

>
> > int a_bit=0,b_bit=0;
> > for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
> >         sum=a_bit+b_bit+carry;
> >         switch(sum){
> >                 case 0: carry=0;//this bit in c is already 0
> >                         break;
> >                 case 1: //make this bit in c 1
> >                         carry=0;
> >                         break;
> >                 case 2: //make this bit zero and carry=1
> >                         //this bit is already zero
> >                         carry=1;
> >                         break;
> >                 case 3: //make this bit 1 and carry =1
> >                         carry=1;
> >                         break;
> >                 default: printf("this must not have happened \n");
> >                          return -1;
> >                 }

>
> > }
> > return c;
> > }

>
> > And one more thing does the C standard specify that for an integral
> > number the MSB is a sign bit or does it say something  about the bit
> > representation of types??

>
> You want to do some variant of
>
> sum     = a ^ b ^ carry
> carry[i+1] = (a & carry) | (b & carry) | (a & b)
>

but creating this array representation of 'a' and 'b' and then
converting 'c' from an array to an integer is more troublesome than
what i wrote i believe.
Mohan
> Tom

mohangupta13, Dec 14, 2009
4. ### Tom St DenisGuest

On Dec 14, 9:44 am, mohangupta13 <> wrote:
> On Dec 14, 6:34 pm, Tom St Denis <> wrote:
>
> > On Dec 14, 8:12 am, mohangupta13 <> wrote:

>
> > > Hello all , I just came across an interesting question .
> > > Q. Add two numbers using bit operations in C?

>
> > > I came up with the below solution .Though it does work , But I believe
> > > there must be a better way to solve this question . Please provide
> > > your inputs .

>
> > > int add(int a,int b){

>
> > > int c=0; //answer
> > > int a_bit=0,b_bit=0;
> > > for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
> > >         sum=a_bit+b_bit+carry;
> > >         switch(sum){
> > >                 case 0: carry=0;//this bit in c is already 0
> > >                         break;
> > >                 case 1: //make this bit in c 1
> > >                         carry=0;
> > >                         break;
> > >                 case 2: //make this bit zero and carry=1
> > >                         //this bit is already zero
> > >                         carry=1;
> > >                         break;
> > >                 case 3: //make this bit 1 and carry =1
> > >                         carry=1;
> > >                         break;
> > >                 default: printf("this must not have happened \n");
> > >                          return -1;
> > >                 }

>
> > > }
> > > return c;
> > > }

>
> > > And one more thing does the C standard specify that for an integral
> > > number the MSB is a sign bit or does it say something  about the bit
> > > representation of types??

>
> > You want to do some variant of

>
> > sum     = a ^ b ^ carry
> > carry[i+1] = (a & carry) | (b & carry) | (a & b)

>
> but creating this array representation of 'a' and 'b' and then
> converting 'c' from an array to an integer is more troublesome than
> what i wrote i believe.
> Mohan
>

I never said you had to make arrays.

Tom

Tom St Denis, Dec 14, 2009
5. ### Jens Thoms ToerringGuest

mohangupta13 <> wrote:
> On Dec 14, 6:34Â pm, Tom St Denis <> wrote:
> > On Dec 14, 8:12Â am, mohangupta13 <> wrote:
> >
> > > Hello all , I just came across an interesting question .
> > > Q. Add two numbers using bit operations in C?

> >
> > > I came up with the below solution .Though it does work , But I believe
> > > there must be a better way to solve this question . Please provide
> > > your inputs .

> >
> > > int add(int a,int b){

> >
> > > int c=0; //answer
> > > int a_bit=0,b_bit=0;
> > > for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
> > > Â  Â  Â  Â  mask=1<<i;
> > > Â  Â  Â  Â  a_bit=a&mask?1:0;
> > > Â  Â  Â  Â  b_bit=b&mask?1:0;
> > > Â  Â  Â  Â  sum=a_bit+b_bit+carry;
> > > Â  Â  Â  Â  switch(sum){
> > > Â  Â  Â  Â  Â  Â  Â  Â  case 0: carry=0;//this bit in c is already 0
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  break;
> > > Â  Â  Â  Â  Â  Â  Â  Â  case 1: //make this bit in c 1
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  c|=mask;
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  carry=0;
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  break;
> > > Â  Â  Â  Â  Â  Â  Â  Â  case 2: //make this bit zero and carry=1
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  //this bit is already zero
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  carry=1;
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  break;
> > > Â  Â  Â  Â  Â  Â  Â  Â  case 3: //make this bit 1 and carry =1
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  c|=mask;
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  carry=1;
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  break;
> > > Â  Â  Â  Â  Â  Â  Â  Â  default: printf("this must not have happened \n");
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â return -1;
> > > Â  Â  Â  Â  Â  Â  Â  Â  }

> >
> > > }
> > > return c;
> > > }

> >
> > > And one more thing does the C standard specify that for an integral
> > > number the MSB is a sign bit or does it say something Â about the bit
> > > representation of types??

> >
> > You want to do some variant of
> >
> > sum Â  Â  = a ^ b ^ carry
> > carry[i+1] = (a & carry) | (b & carry) | (a & b)
> >

> but creating this array representation of 'a' and 'b' and then
> converting 'c' from an array to an integer is more troublesome than
> what i wrote i believe.

> > > sum=a_bit+b_bit+carry;

just that you add bits instead of the whole number while you
explicitely wrote that you had to use bitwise operators which
'+' isn't. By the way, the topmost bit of your result will
never be set, whatever the input...

Regards, Jens
--
\ Jens Thoms Toerring ___
\__________________________ http://toerring.de

Jens Thoms Toerring, Dec 14, 2009
6. ### mohangupta13Guest

On Dec 14, 8:08 pm, (Jens Thoms Toerring) wrote:
> mohangupta13 <> wrote:
> > On Dec 14, 6:34 pm, Tom St Denis <> wrote:
> > > On Dec 14, 8:12 am, mohangupta13 <> wrote:

>
> > > > Hello all , I just came across an interesting question .
> > > > Q. Add two numbers using bit operations in C?

>
> > > > I came up with the below solution .Though it does work , But I believe
> > > > there must be a better way to solve this question . Please provide
> > > > your inputs .

>
> > > > int add(int a,int b){

>
> > > > int c=0; //answer
> > > > int mask=0,carry=0,sum=0,i;
> > > > int a_bit=0,b_bit=0;
> > > > for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
> > > >         sum=a_bit+b_bit+carry;
> > > >         switch(sum){
> > > >                 case 0: carry=0;//this bit in c is already 0
> > > >                         break;
> > > >                 case 1: //make this bit in c 1
> > > >                         carry=0;
> > > >                         break;
> > > >                 case 2: //make this bit zero and carry=1
> > > >                         //this bit is already zero
> > > >                         carry=1;
> > > >                         break;
> > > >                 case 3: //make this bit 1 and carry =1
> > > >                         carry=1;
> > > >                         break;
> > > >                 default: printf("this must not have happened \n");
> > > >                          return -1;
> > > >                 }

>
> > > > }
> > > > return c;
> > > > }

>
> > > > And one more thing does the C standard specify that for an integral
> > > > number the MSB is a sign bit or does it say something  about the bit
> > > > representation of types??

>
> > > You want to do some variant of

>
> > > sum     = a ^ b ^ carry
> > > carry[i+1] = (a & carry) | (b & carry) | (a & b)

>
> > but creating this array representation of 'a' and 'b' and then
> > converting 'c' from an array to an integer is more troublesome than
> > what i wrote i believe.

>
>
> > > >  sum=a_bit+b_bit+carry;

>

I don't know should this be allowed or not .

> just that you add bits instead of the whole number while you
> explicitely wrote that you had to use bitwise operators which
> '+' isn't. By the way, the topmost bit of your result will
> never be set, whatever the input...

well i agree that , but that is not much difficult you can easily see
if the sum is positive or negative and set the bit accordingly ,

>
>                                 Regards, Jens
> --
>   \   Jens Thoms Toerring  ___
>    \__________________________      http://toerring.de

mohangupta13, Dec 14, 2009
7. ### mohangupta13Guest

On Dec 14, 7:46 pm, Tom St Denis <> wrote:
> On Dec 14, 9:44 am, mohangupta13 <> wrote:
>
>
>
> > On Dec 14, 6:34 pm, Tom St Denis <> wrote:

>
> > > On Dec 14, 8:12 am, mohangupta13 <> wrote:

>
> > > > Hello all , I just came across an interesting question .
> > > > Q. Add two numbers using bit operations in C?

>
> > > > I came up with the below solution .Though it does work , But I believe
> > > > there must be a better way to solve this question . Please provide
> > > > your inputs .

>
> > > > int add(int a,int b){

>
> > > > int c=0; //answer
> > > > int mask=0,carry=0,sum=0,i;
> > > > int a_bit=0,b_bit=0;
> > > > for(i=0;i<(pos-1);i++){//pos-1 to leave the MSB as its a sign bit
> > > >         sum=a_bit+b_bit+carry;
> > > >         switch(sum){
> > > >                 case 0: carry=0;//this bit in c is already 0
> > > >                         break;
> > > >                 case 1: //make this bit in c 1
> > > >                         carry=0;
> > > >                         break;
> > > >                 case 2: //make this bit zero and carry=1
> > > >                         //this bit is already zero
> > > >                         carry=1;
> > > >                         break;
> > > >                 case 3: //make this bit 1 and carry =1
> > > >                         carry=1;
> > > >                         break;
> > > >                 default: printf("this must not have happened \n");
> > > >                          return -1;
> > > >                 }

>
> > > > }
> > > > return c;
> > > > }

>
> > > > And one more thing does the C standard specify that for an integral
> > > > number the MSB is a sign bit or does it say something  about the bit
> > > > representation of types??

>
> > > You want to do some variant of

>
> > > sum     = a ^ b ^ carry
> > > carry[i+1] = (a & carry) | (b & carry) | (a & b)

>
> > but creating this array representation of 'a' and 'b' and then
> > converting 'c' from an array to an integer is more troublesome than
> > what i wrote i believe.
> > Mohan

>
> I never said you had to make arrays.
>
> Tom

sorry tom , i didn't think much before speaking ...

int pos=sizeof(int)*8; //numbits
int c=0; //ans
int i;
int carry=0;
int sum=0;
int a_bit=0,b_bit=0;
for(i=0;i<(pos);i++){
sum=a_bit^b_bit^carry;
c|= (sum<<i);
carry= ( (a_bit&b_bit)| (a_bit&carry) | (b_bit&carry) ) ;
}
return c;
}

Any further suggestion for improvement or any other way to do it ??

Mohan

mohangupta13, Dec 14, 2009
8. ### Paul NGuest

On 14 Dec, 13:12, mohangupta13 <> wrote:
> Hello all , I just came across an interesting question .
> Q. Add two numbers using bit operations in C?

int add(int a, int b) {
int c;
do {
c = a & b;
a ^= b;
b = c << 1; } while(c);
return a;
}

Paul.

Paul N, Dec 14, 2009
9. ### Guest

mohangupta13 <> wrote:
>
> Hello all , I just came across an interesting question .
> Q. Add two numbers using bit operations in C?

{

while (b != 0) {
unsigned c = (a & b) << 1;
a ^= b;
b = c;
}
return a;
}
--
Larry Jones

You know how Einstein got bad grades as a kid? Well MINE are even WORSE!
-- Calvin

, Dec 14, 2009
10. ### Barry SchwarzGuest

On Mon, 14 Dec 2009 10:27:10 -0800 (PST), mohangupta13
<> wrote:

snip

How about using horizontal white space (and doing so consistently) so
your code doesn't end up looking like an eye test.

>
>
>int pos=sizeof(int)*8; //numbits
>int c=0; //ans
>int i;
>int carry=0;
>int sum=0;
>int a_bit=0,b_bit=0;
>for(i=0;i<(pos);i++){
> sum=a_bit^b_bit^carry;
> c|= (sum<<i);
> carry= ( (a_bit&b_bit)| (a_bit&carry) | (b_bit&carry) ) ;
>}
>return c;
>}
>
>
>Any further suggestion for improvement or any other way to do it ??
>
>Mohan

--
Remove del for email

Barry Schwarz, Dec 15, 2009
11. ### Peter NilssonGuest

wrote:
> mohangupta13 <> wrote:
> > Hello all , I just came across an interesting question.
> > Q. Add two numbers using bit operations in C?

>
> unsigned add(unsigned a, unsigned b)
> {
>
>   while (b != 0) {
>      unsigned c = (a & b) << 1;
>      a ^= b;
>      b = c;
>   }
>   return a;
> }

Without the temp...

{
while (b) { a ^= b; b &= ~a; b <<= 1; }
return a;
}

The average (for both) is 3 loop iterations. Worst case is
1 more than the width. A good reason to use + instead!

--
Peter

Peter Nilsson, Dec 15, 2009
12. ### Hallvard B FurusethGuest

Peter Nilsson writes:
> Without the temp...
>
> unsigned add(unsigned a, unsigned b)
> {
> while (b) { a ^= b; b &= ~a; b <<= 1; }
> return a;
> }

Yo've got a temp, it's just not spelled out in the C code:
A place for storing ~a, since the compiler can't put that in a.

Which, if you're trying to optimize, means you have one instruction
and computation more per loop iteration than the original.

> The average (for both) is 3 loop iterations. Worst case is
> 1 more than the width. A good reason to use + instead!

And to use do-while instead of while. Rearranging to leave an
instruction between computing and using a value (can help pipelining):
do {
unsigned c = b;
b &= a;
a ^= c;
} while ((b <<= 1) != 0);

Getting back to mohangupta13's questions:

> And one more thing does the C standard specify that for an integral
> number the MSB is a sign bit or does it say something about the bit
> representation of types??

It does say the MSB of a signed integer type is the sign bit. However,
shifting a negative integer has undefined behavior, as has shifting a 1
bit into the sign bit. That's because C allows 3 representations of
signed integers: two's and one's complement, and sign/magnitude.

Which is why you get responses using unsigned integers. No sign bit to
worry about, and overflow is well-defined by modulo (max value + 1)
arithmetic. Except shifting too many bits is not defined.

--
Hallvard

Hallvard B Furuseth, Dec 15, 2009
13. ### Flash GordonGuest

Hallvard B Furuseth wrote:
> Peter Nilsson writes:

<snip>

>> And one more thing does the C standard specify that for an integral
>> number the MSB is a sign bit or does it say something about the bit
>> representation of types??

>
> It does say the MSB of a signed integer type is the sign bit. However,
> shifting a negative integer has undefined behavior,

No, right shifting a negative number has implementation defined behavior
(not undefined) and left shifting it has defined behavior, unless you
are shifting a 0 in to the sign bit.

> as has shifting a 1
> bit into the sign bit.

Only true if it starts off positive (I believe).

> That's because C allows 3 representations of
> signed integers: two's and one's complement, and sign/magnitude.

True in part. I think it is also in part because some processors only
had logical shift instructions, which for any of those representations
would lead to a negative number becoming positive, whilst others had an
arithmetic shift which is effectively the divide by 2 many people expect
a right shift to be.

> Which is why you get responses using unsigned integers. No sign bit to
> worry about, and overflow is well-defined by modulo (max value + 1)
> arithmetic. Except shifting too many bits is not defined.

True.
--
Flash Gordon

Flash Gordon, Dec 15, 2009
14. ### Hallvard B FurusethGuest

Flash Gordon writes:
>Hallvard B Furuseth wrote:
>> It does say the MSB of a signed integer type is the sign bit. However,
>> shifting a negative integer has undefined behavior,

>
> No, right shifting a negative number has implementation defined behavior
> (not undefined)

Sorry, I should have said the shift upthread, i.e. left shift. But:

> and left shifting it has defined behavior, unless you are shifting a 0
> in to the sign bit.
>
>> as has shifting a 1 bit into the sign bit.

>
> Only true if it starts off positive (I believe).

No, and no. C99 6.5.7p4 says about (signed E1) << (valid E2):

(...) If E1 has a signed type and nonnegative value, and E1 * 2**E2
is representable in the result type, then that is the resulting
value; otherwise, the behavior is undefined.

OTOH ANSI C89 3.3.7 does define it: "E1 left-shifted E2 bit positions;
vacated bits are filled with zeros." Maybe there is text elsewhere
which gives more leeway (implemnetation-defined like you say), but
i don't know where.

>> That's because C allows 3 representations of
>> signed integers: two's and one's complement, and sign/magnitude.

>
> True in part. I think it is also in part because some processors only
> had logical shift instructions, which for any of those representations
> would lead to a negative number becoming positive, whilst others had an
> arithmetic shift which is effectively the divide by 2 many people expect
> a right shift to be.

Makes sense. Except I don't get the C89 left-shift requirement to
zero-fill vacated bits. Then one's complement (-x) << 1 == -2x - 1;
to get -2x the implementation must shift in the value of the sign bit.

>> Which is why you get responses using unsigned integers. No sign bit to
>> worry about, and overflow is well-defined by modulo (max value + 1)
>> arithmetic. Except shifting too many bits is not defined.

>
> True.

--
Hallvard

Hallvard B Furuseth, Dec 15, 2009
15. ### Flash GordonGuest

Hallvard B Furuseth wrote:
> Flash Gordon writes:
>> Hallvard B Furuseth wrote:
>>> It does say the MSB of a signed integer type is the sign bit. However,
>>> shifting a negative integer has undefined behavior,

>> No, right shifting a negative number has implementation defined behavior
>> (not undefined)

>
> Sorry, I should have said the shift upthread, i.e. left shift. But:
>
>> and left shifting it has defined behavior, unless you are shifting a 0
>> in to the sign bit.
>>
>>> as has shifting a 1 bit into the sign bit.

>> Only true if it starts off positive (I believe).

>
> No, and no. C99 6.5.7p4 says about (signed E1) << (valid E2):
>
> (...) If E1 has a signed type and nonnegative value, and E1 * 2**E2
> is representable in the result type, then that is the resulting
> value; otherwise, the behavior is undefined.
>
> OTOH ANSI C89 3.3.7 does define it: "E1 left-shifted E2 bit positions;
> vacated bits are filled with zeros." Maybe there is text elsewhere
> which gives more leeway (implemnetation-defined like you say), but
> i don't know where.

OK, I was wrong and it is undefined. That will teach me to make
assumptions ;-) I was probably forgetting about ones complement and
sign-magnitude when I said that.

>>> That's because C allows 3 representations of
>>> signed integers: two's and one's complement, and sign/magnitude.

>> True in part. I think it is also in part because some processors only
>> had logical shift instructions, which for any of those representations
>> would lead to a negative number becoming positive, whilst others had an
>> arithmetic shift which is effectively the divide by 2 many people expect
>> a right shift to be.

>
> Makes sense. Except I don't get the C89 left-shift requirement to
> zero-fill vacated bits. Then one's complement (-x) << 1 == -2x - 1;
> to get -2x the implementation must shift in the value of the sign bit.

<snip>

Probably based on logical left shift instructions, which zero fill.
--
Flash Gordon

Flash Gordon, Dec 15, 2009
16. ### Peter NilssonGuest

Hallvard B Furuseth <> wrote:
> Peter Nilsson writes:
> > Without the temp...
> >
> >   unsigned add(unsigned a, unsigned b)
> >   {
> >     while (b) { a ^= b; b &= ~a; b <<= 1; }
> >     return a;
> >   }

>
> Yo've got a temp, it's just not spelled out in the C code:

In other words, I don't have a temp.

> A place for storing ~a, since the compiler can't put that
> in a.

I didn't ask it to put that into a.

> Which, if you're trying to optimize, means you have one
> instruction and computation more per loop iteration than
> the original.

b &= a; translates to a single PowerPC instruction.

Any sort of micro-optimisation is going to come at a
different cost on different systems. But I was simply
demonstrating that the code could be done without
declaring a third object. [If that's inefficient on
intel platforms... well... everything is inefficient
on intel platforms... ;-]

--
Peter

Peter Nilsson, Dec 16, 2009
17. ### Nick KeighleyGuest

On 14 Dec, 13:12, mohangupta13 <> wrote:

> Hello all , I just came across an interesting question .
> Q. Add two numbers using bit operations in C?

I recall a rather clever recursive solution that was posted on clc
"recently". Unfortunatly the margin of this post is too narrow...

[actually my google skills weren't up to finding it]

Nick Keighley, Dec 16, 2009
18. ### Phil CarmodyGuest

Hallvard B Furuseth <> writes:
> Peter Nilsson writes:
>> Without the temp...
>>
>> unsigned add(unsigned a, unsigned b)
>> {
>> while (b) { a ^= b; b &= ~a; b <<= 1; }
>> return a;
>> }

>
> Yo've got a temp, it's just not spelled out in the C code:
> A place for storing ~a, since the compiler can't put that in a.

B := B AND NOT A may be a primitive operation, and no temporary is
required.

Why don't you complain about the space taken up by the '1'?

And the space taken up by the register copy of all the operands
that has to be made on register-sparse architectures who can't
do everything in registers?

> Which, if you're trying to optimize, means you have one instruction
> and computation more per loop iteration than the original.

Clearly false on architectures which have NAND operations. It's
easy to see how Peter's might be 1 instruction _shorter_ in the
loop than the original.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody, Dec 16, 2009
19. ### Hallvard B FurusethGuest

Peter Nilsson writes:
>Hallvard B Furuseth <> wrote:
>>Peter Nilsson writes:
>>> Without the temp...
>>>
>>>   unsigned add(unsigned a, unsigned b)
>>>   {
>>>     while (b) { a ^= b; b &= ~a; b <<= 1; }
>>>     return a;
>>>   }

>>
>> Yo've got a temp, it's just not spelled out in the C code:

>
> In other words, I don't have a temp.

All right then, you do have temporary (computed) value, but you don't
stuff it into a variable. And it can be optimized away on some
platforms, true. (Not with a nand instruction though, Phil should look
up what nand does.)

[Rearranging a little]
> But I was simply demonstrating that the code could be done without
> declaring a third object.

True enough, rendering the rest of my point moot.

>> A place for storing ~a, since the compiler can't put that
>> in a.

>
> I didn't ask it to put that into a.

I wasn't suggesting that.

>> Which, if you're trying to optimize, means you have one
>> instruction and computation more per loop iteration than
>> the original.

>
> b &= a; translates to a single PowerPC instruction.
>
> Any sort of micro-optimisation is going to come at a
> different cost on different systems.

--
Hallvard

Hallvard B Furuseth, Dec 17, 2009