Velocity Reviews > Addition by bitwise operations.

mohangupta13
Guest
Posts: n/a

 12-14-2009
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

Tom St Denis
Guest
Posts: n/a

 12-14-2009
On Dec 14, 8:12*am, mohangupta13 <(E-Mail Removed)> 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
> * * * * 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[i] = a[i] ^ b[i] ^ carry[i]
carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])

Tom

mohangupta13
Guest
Posts: n/a

 12-14-2009
On Dec 14, 6:34*pm, Tom St Denis <(E-Mail Removed)> wrote:
> On Dec 14, 8:12*am, mohangupta13 <(E-Mail Removed)> 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
> > * * * * 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[i] * * = a[i] ^ b[i] ^ carry[i]
> carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])
>

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

Tom St Denis
Guest
Posts: n/a

 12-14-2009
On Dec 14, 9:44*am, mohangupta13 <(E-Mail Removed)> wrote:
> On Dec 14, 6:34*pm, Tom St Denis <(E-Mail Removed)> wrote:
>
> > On Dec 14, 8:12*am, mohangupta13 <(E-Mail Removed)> 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[i] * * = a[i] ^ b[i] ^ carry[i]
> > carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])

>
> 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
Guest
Posts: n/a

 12-14-2009
mohangupta13 <(E-Mail Removed)> wrote:
> On Dec 14, 6:34Â*pm, Tom St Denis <(E-Mail Removed)> wrote:
> > On Dec 14, 8:12Â*am, mohangupta13 <(E-Mail Removed)> 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[i] Â* Â* = a[i] ^ b[i] ^ carry[i]
> > carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])
> >

> 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://www.velocityreviews.com/forums/(E-Mail Removed)
\__________________________ http://toerring.de

mohangupta13
Guest
Posts: n/a

 12-14-2009
On Dec 14, 8:08*pm, (E-Mail Removed) (Jens Thoms Toerring) wrote:
> mohangupta13 <(E-Mail Removed)> wrote:
> > On Dec 14, 6:34*pm, Tom St Denis <(E-Mail Removed)> wrote:
> > > On Dec 14, 8:12*am, mohangupta13 <(E-Mail Removed)> 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
> > > > * * * * 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[i] * * = a[i] ^ b[i] ^ carry[i]
> > > carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])

>
> > 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 *___ * * *(E-Mail Removed)
> * *\__________________________ * * *http://toerring.de

mohangupta13
Guest
Posts: n/a

 12-14-2009
On Dec 14, 7:46*pm, Tom St Denis <(E-Mail Removed)> wrote:
> On Dec 14, 9:44*am, mohangupta13 <(E-Mail Removed)> wrote:
>
>
>
> > On Dec 14, 6:34*pm, Tom St Denis <(E-Mail Removed)> wrote:

>
> > > On Dec 14, 8:12*am, mohangupta13 <(E-Mail Removed)> 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
> > > > * * * * 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[i] * * = a[i] ^ b[i] ^ carry[i]
> > > carry[i+1] = (a[i] & carry[i]) | (b[i] & carry[i]) | (a[i] & b[i])

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

Paul N
Guest
Posts: n/a

 12-14-2009
On 14 Dec, 13:12, mohangupta13 <(E-Mail Removed)> 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.

lawrence.jones@siemens.com
Guest
Posts: n/a

 12-14-2009
mohangupta13 <(E-Mail Removed)> 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

Barry Schwarz
Guest
Posts: n/a

 12-15-2009
On Mon, 14 Dec 2009 10:27:10 -0800 (PST), mohangupta13
<(E-Mail Removed)> 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