When I was in 12th Grade High School, I asked myself how a computer can do arithmetic. I had already programming Pascal since I was in Grade 7th, and I don’t know much about logic gates, yet at that time. But I know that in its very basic form, computer can only do logical operation such as AND, OR, NOT, XOR, SHL and SHR, so I asked myself, how can I make a function in capable to do addition without the use of the sign “+” in the program. These are the steps I take :

First, I make a truth table for basic binary addition in order to know what is needed in the function :

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10

Then I realize that the right hand side of the addition process above must be two bits long instead of only one bit, so I rewrite them in the form below

0 + 0 = 00

0 + 1 = 01

1 + 0 = 01

1 + 1 = 10

Later, I compare the truth table for several logic gates with the result I got above, it turn out that :

- the least significant bit, which I called R, show XOR logical relationship with the input.

R = A xor B .…(E1)

- the most significant bit, which I called C, show AND logical relationship with the input.

C = A and B ….(E2)

Since in its basic form the equation must be in the form of :

A + B = C shl 1 + R ….(E3)

By substituting E1 and E2 to equation E3 we got equation E4, below :

A + B = (A and B) shl 1 + (A xor B) ….(E4)

Then I write a Pascal recursive function capable of doing addition without using the sign “+”.

function AddLogic(const A : integer, B : integer) : integer;

var R,C : integer;

begin

R:=A xor B;

C:=(A and B) shl 1;

if (R=0) then R:=C;

else R:=AddLogic(R,C);

AddLogic:=VN;

end;

I realize later that I can do away with the recursive bit, by using repetition.

function AddLogic(const A : integer, B : integer) : integer;

var A1,B1,R,C : integer;

begin

A1:=A;

B1:=B;

repeat

R:=A1 xor B1;

C:=(A1 and B1) shl 1;

A1:=R;

B1:=C;

until (C=0) or (R=0);

if (R=0) then R:=C;

AddLogic:=VN;

end;

Which later I translate to C.

int AddLogic( int A, int B)

{ int A1,B1,R,C;

A1=A;

B1=B;

do

{ R=A1^B1;

C=(A1&B1)<<1;

A1=R;

B1=C;

} while (C&R);

if C R=C;

return R;

}

These programs didn't run as fast as if I just use the sign "+", which is a proof that something is still missing from my understanding. Later I realize that this level of detail is done in hardware layer instead of software layer. I will tell you what is missing in later posting.

## Tuesday, January 22, 2008

### Making Arithmetic function from Logical function ( Pascal, C )

Labels:
from logic gate to computer

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment