Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Addition by bitwise operations.

Reply
Thread Tools

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
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
 
Reply With Quote
 
 
 
 
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
> 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])

Tom

 
Reply With Quote
 
 
 
 
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
> > 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
> Tom


 
Reply With Quote
 
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 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
 
Reply With Quote
 
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 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.


But your solution is cheating since you use an addition

> > > 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
 
Reply With Quote
 
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.

>
> But your solution is cheating since you use an addition
>
> > > > *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


 
Reply With Quote
 
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 ...

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
 
Reply With Quote
 
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?


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.
 
Reply With Quote
 
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?


unsigned add(unsigned a, unsigned b)
{

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
 
Reply With Quote
 
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 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.

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


--
Remove del for email
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
about addition operator jiten VHDL 3 06-23-2005 05:26 AM
Beginners questions for addition Clemens Bosch VHDL 0 12-02-2004 02:20 PM
Addition of one Julian VHDL 13 10-21-2004 05:46 AM
Office Development (feature addition) Midnight Java Junkie ASP .Net 0 06-20-2004 07:24 AM
Queston about addition in Maxplus II lezah VHDL 7 03-02-2004 06:11 PM



Advertisments