Boolean Arithmetic

Building a Modern Computer From First Principles

www.nand2tetris.org

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 1
Usage and Copyright Notice:

Copyright © Noam Nisan and Shimon Schocken

This presentation contains lecture materials that accompany the textbook “The Elements of
Computing Systems” by Noam Nisan & Shimon Schocken, MIT Press, 2005.

We provide both PPT and PDF versions.

Our web site, www.nand2tetris.org ,features a set of presentations, one for each book chapter.
Each presentation is designed to support about 3 hours of classroom or self-study instruction.

You are welcome to use or edit this presentation as you see fit for instructional and non-
commercial purposes.

If you use our materials, please include a reference to www.nand2tetris.org

If you have any questions or comments, please write us at [email protected]

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 2
Counting systems

quantity decimal binary 3-bit register

0 0 000

 1 1 001

 2 10 010

 3 11 011

 4 100 100

 5 101 101

 6 110 110

 7 111 111

 8 1000 overflow

 9 1001 overflow

 10 1010 overflow

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 3
Rationale

(9038) ten  9 103  0 10 2  3 101  8 100  9038

(10011) two  1  2 4  0  2 3  0  2 2  1  21  1  2 0  19

n
( xn xn1 ...x0 ) b   xi  b i

i 0

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 4
Binary addition

Assuming a 4-bit system:

0 0 0 1 1 1 1 1
1 0 0 1 + 1 0 1 1+
0 1 0 1 0 1 1 1

0 1 1 1 0 1 0 0 1 0

no overflow overflow

 Algorithm: exactly the same as in decimal addition

 Overflow (MSB carry) has to be dealt with.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 5
Representing negative numbers (4-bit system)

 The codes of all positive numbers

0 0000
begin with a “0”
1 0001 1111 -1
2 0010 1110 -2  The codes of all negative numbers
3 0011 1101 -3 begin with a “1“
4 0100 1100 -4  To convert a number:
5 0101 1011 -5 leave all trailing 0’s and first 1 intact,
6 0110 1010 -6 and flip all the remaining bits
7 0111 1001 -7
1000 -8

Example: 2 - 5 = 2 + (-5) = 0010

+1011
1101 = -3
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 6
Building an Adder chip

 Adder: a chip designed to add two integers

 Proposed implementation:
 Half adder: designed to add 2 bits
 Full adder: designed to add 3 bits
 Adder: designed to add two n-bit numbers.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 7
Half adder (designed to add 2 bits)

a b sum carry

0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Implementation: based on two gates that you’ve seen before.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 8
Full adder (designed to add 3 bits)

a b c sum carry

0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Implementation: can be based on half-adder gates.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 9
n-bit Adder (designed to add two 16-bit numbers)

... 1 0 1 1 a
+
… 0 0 1 0 b

… 1 1 0 1 out

Implementation: array of full-adder gates.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 10
The ALU (of the Hack platform)

out(x, y, control bits) =

x+y, x-y, y–x,

0, 1, -1,
x, y, -x, -y,
x!, y!,
x+1, y+1, x-1, y-1,
x&y, x|y

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 11
ALU logic (Hack platform)

Implementation: build a logic gate architecture

that “executes” the control bit “instructions”:
if zx==1 then set x to 0 (bit-wise), etc.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 12
The ALU in the CPU context (a sneak preview of the Hack platform)

c1,c2, … ,c6

D
D register

a
out

ALU
A
A register

A/M

Mux
RAM M

(selected
register)

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 13
Perspective

 Combinational logic

 Our adder design is very basic: no parallelism

 It pays to optimize adders

 Our ALU is also very basic: no multiplication, no division

 Where is the seat of more advanced math operations?

a typical hardware/software tradeoff.

Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 14
Historical end-note: Leibnitz (1646-1716)

 “The binary system may be used in place of the decimal system;

express all numbers by unity and by nothing”

 1679: built a mechanical calculator (+, -, *, /)

 CHALLENGE: “All who are occupied with the reading

or writing of scientific literature have assuredly
very often felt the want of a common scientific
language, and regretted the great loss of time and
trouble caused by the multiplicity of languages
employed in scientific literature:
Leibniz’s medallion
 SOLUTION: “Characteristica Universalis”: a for the Duke of Brunswick
universal, formal, and decidable language of
reasoning
 The dream’s end: Turing and Gödel in 1930’s.
Elements of Computing Systems, Nisan & Schocken, MIT Press, www.nand2tetris.org , Chapter 2: Boolean Arithmetic slide 15