Addition by bitwise operations.
mohangupta13
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
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
converting 'c' from an array to an integer is more troublesome than
what i wrote i believe.
Mohan
> Tom
Tom St Denis
I never said you had to make arrays.
Tom
Jens Thoms Toerring
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 ___ j...@toerring.de
\__________________________ http://toerring.de
mohangupta13
> 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
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.
lawrenc...@siemens.com
>
> 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
Barry Schwarz
<mohang...@gmail.com> 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
Peter Nilsson
> mohangupta13 <mohangupt...@gmail.com> 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
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.
--
Hallvard
Flash Gordon
> 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
Hallvard B Furuseth
>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
Flash Gordon
> 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
Peter Nilsson
> 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
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
> 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
Hallvard B Furuseth
>Hallvard B Furuseth <h.b.furus...@usit.uio.no> 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