Addition by bitwise operations.

[mohangupta13]

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
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??

Thanks
Mohan Gupta

 

[Tom St Denis]

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
        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)

Tom

 

[mohangupta13]

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
        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.
Mohan

 

[Tom St Denis]

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

 

[Jens Thoms Toerring]

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
        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.

But your solution is cheating since you use an addition

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

 

[mohangupta13]

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
        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.

But your solution is cheating since you use an addition

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 ,

 

[mohangupta13]

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
        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.
Mohan

I never said you had to make arrays.

Tom

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

how about this new implementation

int add(int a,int b){

int pos=sizeof(int)*8; //numbits
int c=0; //ans
int i;
int mask=0;
int carry=0;
int sum=0;
int a_bit=0,b_bit=0;
for(i=0;i<(pos);i++){
mask=1<<i;
a_bit=a&mask?1:0;
b_bit=b&mask?1:0;
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

 

[Paul N]

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

How about the following?

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

Paul.

 

[lawrence.jones]

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;
}

 

[Barry Schwarz]

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

snip

how about this new implementation

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

 

[Peter Nilsson]

unsigned add(unsigned a, unsigned b)
{

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

Without the temp...

unsigned add(unsigned a, unsigned b)
{
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!

 

[Hallvard B Furuseth]

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.

 

[Flash Gordon]

Peter Nilsson writes:


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.

 

[Hallvard B Furuseth]

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.


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.

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.

 

[Flash Gordon]

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


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.

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.

 

[Peter Nilsson]

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... ;-]

 

[Nick Keighley]

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]

 

[Phil Carmody]

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

 

[Hallvard B Furuseth]

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.

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

I wasn't suggesting that.