# Re: hw4, P5

Himanshu Nautiyal (nautiyal@cs.washington.edu)
Mon, 10 Feb 1997 17:54:38 -0800 (PST)

> On P5, my 4-bit Carry lookahead ALU is able to do addition correctly. But
> for 6-3, I got 2, which seems correct to me since:
>
> 6 = 0 1 1 0
>
> 3 = 0 0 1 1
> -3 = 1 1 0 0 (1's compl.)

But to be able to do subtraction as addition of a complement, we
have to use TWO's complement, not ones. If you are mathematically
inclined, please look below my signature for the proof.

For the rest, note that the two's complemment of 3 is
1101. when we do

6 = 0 1 1 0
-3 = 1 1 0 1
-------------
1 0 0 1 1

of which we use only the last 4 bits to get 3, the correct answer.

Himanshu Nautiyal
http://www.cs.washington.edu/homes/nautiyal

------------------------------------------------------------------------
sketch of proof. Dont worry if you dont understand it.

Note that given 8 bits, we can represent numbers from -128 to 127. Notice
that for a given negative number, say -3, its representation (ie. the
two's complement i.e. 11111101, when considered as a non-negative number is
just 253 = 256 - 3. So when do x - 3 by doing x + (-3) as non-negative

x + (256 - 3)
= (x - 3) + 256.

The 256 appears as a carry out from the 8th bit, which we dont look at
anyway (except to check for overflow), thus we only look at the (x - 3)