Is there a way to perform addition(or arithmetic operations) by using ONLY bitwise operators?
3 Answers
You can search for some hardware designs for arithmetic operators. For addition example, you can find full adder, half adder, then ripple carry adder, carry save adder, carry lookahead adder. Then you can generate lots of code to use bit-wise operators to do those arithmetic operations.
6 Comments
kevintodisco
I would make it more clear in this answer that the only way that hardware performs addition and other arithmetic operations is with bitwise logical operations :)
jogojapan
@ktodisco But from that it doesn't follow that C/C++ bitwise operators can be used to describe these operations. There is a difference between bitwise operations in general, and the bitwise operators of C/C++.
Voo
@jogojapan There is? Yes the right shift is annoyingly unspecified, but you can fix that rather easily with a bit extra code and it's not as if implementing right shifts with a bit of looping and the more elemental bitwise operators was especially complicated.
jogojapan
@Voo What I mean is that for example the processor instruction ADD is of course a bitwise operation. When it is applied to two registers, it will perform addition by manipulating the bits in of the target register as necessary. But who says that this operation can be expressed using no more than
&, |, ~? (We know it can, but this doesn't follow trivially from the fact that ADD is applied in a bitwise manner.)Voo
Hmm no, I don't see how from "Add is implemented using only bitwise operations" it doesn't follow that "We can implement add using only bitwise operations". Whether I do the operations on paper, in my head, in a high level language like c++ or using 32nm CMOS transistors is rather immaterial really.
|
Addition of bits a,b and c
carry_out = b&c|a&b|a&c; // there's a carry, if at least 2 bits are set
sum = a^b^c; // the sum is the number of set bits modulo 2
One has to perform this for all bits in the word - first for bit 0 using carry_in = c = 0, and iterating to carry_in(next_bit) = carry_out(previous_result).
Subtraction happens with bit inverting b from (a-b) and setting the initial carry to 1.
However, if one has to add e.g 32 numbers in parallel, one can fit 'a' with 32 lsbs of all those numbers and perform the binary operations in parallel. This is a technique called bit slicing.
For multiplication CSA (carry save adder is definitely the best software approach -- it has the smallest "area")
As an exercise, here's an algorithm that calculates a+b(+c) in parallel:
int a = 13113;
int b = 43334;
int c = 1;
int main()
{
int sum=a^b^c,c2;
c=((c&a)|(a&b)|(c&b))<<1;
while (c) {
c2=(c&sum)<<1;
sum^=c;
c=c2;
}
printf("%d\n",sum);
}
Comments
Note that bitwise operators in C is only applicable to integral operands not on arithmetic operands
And yes you can do it using bitwise for all operations(+,-,*,/,%)
for e.g.
int a =10;
a<<1; // it's multiplication : a*2
a>>1; //it's division : a/2
I have shown this for 2 only.
You can do for addition of two integers using the FULL ADDER (SUM and CARRY functios) for any number of bits
log10is done bitwise.