Addition by bitwise operations.

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

  1. mohangupta13

    mohangupta13 Guest

    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
     
    mohangupta13, Dec 14, 2009
    #1
    1. Advertising

  2. mohangupta13

    Tom St Denis Guest

    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
    >         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
     
    Tom St Denis, Dec 14, 2009
    #2
    1. Advertising

  3. mohangupta13

    mohangupta13 Guest

    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
    > >         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
     
    mohangupta13, Dec 14, 2009
    #3
  4. mohangupta13

    Tom St Denis Guest

    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
    > > >         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
     
    Tom St Denis, Dec 14, 2009
    #4
  5. 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
    > > >         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

    > > > 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
    #5
  6. mohangupta13

    mohangupta13 Guest

    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
    > > > >         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
    >
    > > > >  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
    #6
  7. mohangupta13

    mohangupta13 Guest

    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
    > > > >         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
     
    mohangupta13, Dec 14, 2009
    #7
  8. mohangupta13

    Paul N Guest

    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?


    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.
     
    Paul N, Dec 14, 2009
    #8
  9. mohangupta13

    Guest

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

    You know how Einstein got bad grades as a kid? Well MINE are even WORSE!
    -- Calvin
     
    , Dec 14, 2009
    #9
  10. On Mon, 14 Dec 2009 10:27:10 -0800 (PST), mohangupta13
    <> 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
     
    Barry Schwarz, Dec 15, 2009
    #10
  11. 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...

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

    --
    Peter
     
    Peter Nilsson, Dec 15, 2009
    #11
  12. 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
    #12
  13. mohangupta13

    Flash Gordon Guest

    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
    #13
  14. 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
    #14
  15. mohangupta13

    Flash Gordon Guest

    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
    #15
  16. 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
    #16
  17. 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
    #17
  18. mohangupta13

    Phil Carmody Guest

    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
    #18
  19. 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
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?Sm9u?=

    BitWise Operations

    =?Utf-8?B?Sm9u?=, Jan 23, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    3,380
    =?Utf-8?B?Sm9u?=
    Jan 24, 2006
  2. E. Robert Tisdale

    Re: seeking bitwise operations solution

    E. Robert Tisdale, Aug 17, 2003, in forum: C Programming
    Replies:
    4
    Views:
    453
  3. Carl
    Replies:
    3
    Views:
    4,105
    John Machin
    Aug 19, 2005
  4. Chris
    Replies:
    6
    Views:
    2,424
    Daniel Pitts
    Jan 5, 2007
  5. Alan Holloway

    newbie seeks insight on bitwise operations..

    Alan Holloway, Jul 28, 2004, in forum: C Programming
    Replies:
    11
    Views:
    441
    Keith Thompson
    Jul 30, 2004
Loading...

Share This Page