CS 15
CS 15 -- Homework 2 Binary Subtraction
<![CDATA[
cfk's 'mechanical' procedure for binary subtraction:
This looks best with a fixed width font like
Courier 12.
The 'mechanical' procedure:
Let D = M - S. That is D is the difference between M and S that
we are seeking.
Let the digits of M be m(n-1), m(n-2), ..., m(2), m(1), m(0).
Let the digits of S be s(n-1), s(n-2), ..., s(2), s(1), s(0).
We seek the digits of D: d(n-1), d(n-2), ..., d(2), d(1), d(0).
We work from right to left.
1) Initially make k = 0.
2) If m(k) = s(k), make d(k) = 0,
if m(k) = 1 and s(k) = 0, make d(k) = 1,
otherwise, starting at column (k+1), move left through the
digits of M changing 0s to 1s until you get to a 1. Change
that to a 0, make d(k) = 1.
3) increase k by 1.
4) if k < n return to 2), otherwise stop,
d(n-1), d(n-2), ..., d(1), d(0) is the answer.
==============================================================
An example:
For example, if n = 9 and M = 100100011, then
m(8) = 1, m(7) = 0, m(6) = 0, m(5) = 1, m(4) = 0, m(3) = 0,
m(2) = 0, m(1) = 1, m(0) = 1.
Suppose S = 001001110, then we start with
position 876543210
M 100100011
- S - 001001110
--------------------
D ?????????
start the procedue with k = 0
rule 2) says make d(0) = 1
with k = 1
rule 2) says make d(1) = 0
with k = 2
rule 2) says change m(3) and m(4) to 1 and m(5) to 0,
make d(2) = 1,
by the time rule 3) increases k to 3, the remaining problem
looks like:
position 876543210
M 100011x11
- S - 001001110
--------------------
D ??????101
continuing with the procedure, we end up with
D = 011010101
end example
=========================================================
]]>