PowerPoint Presentation
Chapter 2
Boolean Arithmetic
From Nand to Tetris
Building a Modern Computer from First Principles
These slides support chapter 2 of the book
The Elements of Computing Systems
By Noam Nisan and Shimon Schocken
MIT Press
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
You are welcome to use this presentation, or any part of it,
in Nand to Tetris courses, or in other courses, as you see fit.
Usage is free provided that it supports instruction in an educational,
non-profit setting.
Feel free to use the slides as-is, or modify them as needed.
We’ll appreciate it if you will give credit somewhere to Nand to Tetris,
and put a reference to www.nand2tetris.org
You are welcome to remove this slide from the presentation. If you make extensive changes to the slides, you can remove the copyright notice also.
Happy teaching!
Noam Nisam / Shimon Schocken
Usage Notice
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 1
00 01 10 11
3 bits – 8 possibilities
N bits – 2N possibilities
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers
Binary Decimal
0 0
1 1
10 2
11 3
100 4
101 5
…
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers
7 8 9 ten
100s 10s 1s
102 101 100
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers
7 8 9 ten
= 7・102 + 8・101 + 9・100 = 789 ten
100s 10s 1s
102 101 100
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
1 0 1two
4s 2s 1s
22 21 20
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
1 0 1two
= 1・102 + 0・101 + 1・100 = 5 ten
4s 2s 1s
22 21 20
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
bn bn-1 bn-2 … b1 b0
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
bn bn-1 bn-2 … b1 b0
=
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary Decimal
bn bn-1 bn-2 … b1 b0
Maximum value represented by k bits:
1 + 2 + 4 + … + 2k-1 = 2k-1
=
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size
We will use a fixed number of bits.
Say 8 bits.
0000 0000
0000 0001
0000 0010
0000 0011
…
0111 1111
1000 0000
1000 0001
…
1111 1110
1111 1111
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Fixed word size
We will use a fixed number of bits.
Say 8 bits.
0000 0000
0000 0001
0000 0010
0000 0011
…
0111 1111
1000 0000
1000 0001
…
1111 1110
1111 1111
28 = 256 values
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing signed numbers
positive values
negative values
We will use a fixed number of bits.
Say 8 bits.
0000 0000
0000 0001
0000 0010
0000 0011
…
0111 1111
1000 0000
1000 0001
…
1111 1110
1111 1111
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing signed numbers
positive values
negative values
We will use a fixed number of bits.
Say 8 bits.
0000 0000
0000 0001
0000 0010
0000 0011
…
0111 1111
1000 0000
1000 0001
…
1111 1110
1111 1111
That’s one possible representation
We’ll use a better one, later
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = ? ? ? ? ? ? ? ? two
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4 + 2
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4 + 2 + 1
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4 + 2 + 1
= ? ? ? ? ? ? ? ? two
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4 + 2 + 1
= 0 1 0 1 0 1 1 1 two
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Decimal Binary
87ten = 64 + 16 + 4 + 2 + 1
= 0 1 0 1 0 1 1 1 two
32 8
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Boolean arithmetic
Addition
Subtraction
Comparison (<,>,=)
Multiplication
Division
implement
get for free
postpone
to software
postpone
to software
get for free
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92
+
Addition
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92
113
+
Addition
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1 21
0 1 0 1 1 1 0 0 92
0 1 1 1 0 0 0 1 113
+
Addition
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
5 7 8 3
2 4 5 6
? ? ? ?
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
5 7 8 3
2 4 5 6
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
5 7 8 3
2 4 5 6
9
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1
5 7 8 3
2 4 5 6
3 9
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
5 7 8 3
2 4 5 6
2 3 9
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
5 7 8 3
2 4 5 6
8 2 3 9
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 0 0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 1 0 0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
1 1 1 0 0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 1 1
0 0 0 1 0 1 0 1
0 1 0 1 1 1 0 0
0 1 1 1 0 0 0 1
+
Addition
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Overflow
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 0 0 1 0 1 0 1
1 1 0 1 1 1 0 0
? ? ? ? ? ? ? ?
+
Overflow
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
1 0 0 0 1 1 1 0 0
1 0 0 1 0 1 0 1
1 1 0 1 1 1 0 0
1 0 1 1 1 0 0 0 1
+
Overflow
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Building an Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Building an Adder
Half adder: adds two bits
Full adder: adds three bits
Adder: adds two integers
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Half adder
a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
sum bit
carry bit
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Half adder
/** Computes the sum of two bits. */
CHIP HalfAdder {
IN a, b;
OUT sum, carry;
PARTS:
// Put your code here:
}
HalfAdder.hdl
a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Full adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Full adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Full adder
sum bit
carry bit
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Full adder
/** Computes the sum of three bits. */
CHIP HalfAdder {
IN a, b, c;
OUT sum, carry;
PARTS:
// Put your code here:
}
FullAdder.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Multi-bit Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
0 0 1 0 1 1 0
1 0 0 1 0 1 1 1
0 1 0 1 0 0 1 0
1 1 1 0 1 0 0 1
+
Multi-bit Adder
/* Adds two 16-bit, two’s-complement values.
* The most-significant carry bit is ignored. */
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put you code here:
}
Add16.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers (using 4 bits)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing numbers (using 4 bits)
Using n bits, we can represent
the positive integers in the range
0 … 2n-1
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Representing negative numbers
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Possible solution: use a sign bit
Use the left-most bit to represent the sign, -/+
Use the remaining bits to represent a positive number
Complications:
-0?
x + (-x) is not 0
more complications
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -0
1001 -1
1010 -2
1011 -3
1100 -4
1101 -5
1110 -6
1111 -7
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Represent the negative number -x using the positive number 2n – x
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement
Represent the negative number -x using the positive number 2n – x
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (16 – 8)
1001 -7 (16 – 9)
1010 -6 (16 – 10)
1011 -5 (16 – 11)
1100 -4 (16 – 12)
1101 -3 (16 – 13)
1110 -2 (16 – 14)
1111 -1 (16 – 15)
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Two’s Complement
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (16 – 8)
1001 -7 (16 – 9)
1010 -6 (16 – 10)
1011 -5 (16 – 11)
1100 -4 (16 – 12)
1101 -3 (16 – 13)
1110 -2 (16 – 14)
1111 -1 (16 – 15)
positive numbers range:
0 … 2n-1 – 1
negative numbers range:
-1 … -2n – 1
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
+
14
13
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
+
14
13
+
1110
1101
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
+
14
13
+
1110
1101
11011
+
11011 = 27 ten
1011 = 11 ten
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
+
14
13
11
+
1110
1101
11011
+
11011 = 27 ten
1011 = 27 ten
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Addition using two’s complement
-2
-3
-5
+
14
13
11
+
1110
1101
11011
+
11011 = 27 ten
1011 = 27 ten
Two’s complement rationale:
representation is modulu 2n
addition is modulu 2n
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Insight: if we solve this we’ll know how to subtract:
y – x = y + (-x)
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)
–
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)
01010011
–
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x
Input: x
Output: -x (in two’s complement)
Idea: 2n – x = 1 + (2n – 1) – x
11111111 two
11111111
10101100 (some x example)
01010011 (flip all the bits)
–
Now add 1 to the result
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
Output: 1100
+
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Computing -x (example)
Input: 4
Output: should be 12 (representing -4 in two’s compelemt)
Input: 0100
Flip the bits: 1011
Add one: 1
Output: 1100
= 12 ten
+
To add 1:
Flip all the bits from right to left, stop when the first 0 flips to 1
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Input
Von Neumann Architecture
Memory
Output
CPU
Control
ALU
Computer System
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Input
The Arithmetic Logical Unit
Memory
Output
CPU
Control
ALU
Computer System
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Arithmetic Logical Unit
ALU
f
(input1, input2)
input1
input2
f
f
: one out of a family of pre-defined arithmetic and logical functions
The ALU computes a function on the two inputs, and outputs the result
Arithmetic functions: integer addition, multiplication, division, …
logical functions: And, Or, Xor, …
Which functions should the ALU perform?
A hardware / software tradeoff.
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU
Operates on two 16-bit, two’s complement values
Outputs a 16-bit, two’s complement value
Which function to compute is set by six 1-bit inputs
Computes one out of a family of 18 functions
Also outputs two 1-bit values (to be discussed later).
out
0
1
-1
x
y
!x
!y
-x
-y
x+1
y+1
x-1
y-1
x+y
x-y
y-x
x&y
x|y
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU
out
0
1
-1
x
y
!x
!y
-x
-y
x+1
y+1
x-1
y-1
x+y
x-y
y-x
x&y
x|y
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU
zx nx zy ny f no out
1 0 1 0 1 0 0
1 1 1 1 1 1 1
1 1 1 0 1 0 -1
0 0 1 1 0 0 x
1 1 0 0 0 0 y
0 0 1 1 0 1 !x
1 1 0 0 0 1 !y
0 0 1 1 1 1 -x
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1
1 1 0 1 1 1 y+1
0 0 1 1 1 0 x-1
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y
To cause the ALU to compute a function, set the control bits to one of the binary combinations listed in the table.
control bits
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU in action: compute y-x
Load
tools/builtInChips/ALU.hdl
2. Evaluate
the chip logic
3. Inspect the
ALU outputs
Set the ALU’s inputs and control bits to some test values
(000111 codes “output y-x”)
The built-in ALU implementation has some GUI side-effects
Built-in ALU implementation
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU in action: compute x & y
Set the ALU’s inputs and control bits to some test values
(000000 codes “compute x&y”)
Inspect the
ALU outputs
Set to binary I/O format
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Opening up the Hack ALU black box
x
y
out = f(control bits, x, y)
Hack ALU
control bits
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU operation
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out
out(x,y)=
ALU
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU operation
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out
out(x,y)=
1 0 1 0 1 0 0
1 1 1 1 1 1 1
1 1 1 0 1 0 -1
0 0 1 1 0 0 x
1 1 0 0 0 0 y
0 0 1 1 0 1 !x
1 1 0 0 0 1 !y
0 0 1 1 1 1 -x
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1
1 1 0 1 1 1 y+1
0 0 1 1 1 0 x-1
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out
out(x,y)=
1 0 1 0 1 0 0
1 1 1 1 1 1 1
1 1 1 0 1 0 -1
0 0 1 1 0 0 x
1 1 0 0 0 0 y
0 0 1 1 0 1 !x
1 1 0 0 0 1 !y
0 0 1 1 1 1 -x
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1
1 1 0 1 1 1 y+1
0 0 1 1 1 0 x-1
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y
ALU operation example: compute !x
Example: compute !x
x: 1 1 0 0
y: 1 0 1 1
Following pre-setting:
x: 1 1 0 0
y: 1 1 1 1
Computation and post-setting:
x&y: 1 1 0 0
!(x&y): 0 0 1 1 (!x)
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
ALU operation example: compute y-x
pre-setting
the x input pre-setting
the y input selecting between computing + or & post-setting the output Resulting
ALU output
zx nx zy ny f no out
if zx
then
x=0 if nx
then
x=!x if zy
then
y=0 if ny
then
y=!y if f
then out=x+y
else out=x&y if no
then
out=!out
out(x,y)=
1 0 1 0 1 0 0
1 1 1 1 1 1 1
1 1 1 0 1 0 -1
0 0 1 1 0 0 x
1 1 0 0 0 0 y
0 0 1 1 0 1 !x
1 1 0 0 0 1 !y
0 0 1 1 1 1 -x
1 1 0 0 1 1 -y
0 1 1 1 1 1 x+1
1 1 0 1 1 1 y+1
0 0 1 1 1 0 x-1
1 1 0 0 1 0 y-1
0 0 0 0 1 0 x+y
0 1 0 0 1 1 x-y
0 0 0 1 1 1 y-x
0 0 0 0 0 0 x&y
0 1 0 1 0 1 x|y
Example: compute y-x
x: 0 0 1 0 (2)
y: 0 1 1 1 (7)
Following pre-setting:
x: 0 0 1 0
y: 1 0 0 0
Computation and post-setting:
x+y: 1 0 1 0
!(x+y): 0 1 0 1 (5)
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
The Hack ALU output control bits
if (out == 0) then zr = 1, else zr = 0
if (out < 0) then ng = 1, else ng = 0
These two control bits will come into play when we build the complete computer’s architecture.
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Perspective
The Hack ALU is:
Simple
Elegant
To implement it this ALU,
you only need to know how to:
Set a 16-bit value to 0000000000000000
Set a 16-bit value to 1111111111111111
Negate a 16-bit value (bit-wise)
Compute plus or And on two 16-bit values
That’s it!
“Simplicity is the ultimate sophistication.”
― Leonardo da Vinci
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Project 2
Given: All the chips built in Project 1
HalfAdder
FullAdder
Add16
Inc16
ALU
Goal: Build the following chips:
A family of combinational chips, from simple adders to an Arithmetic Logic Unit.
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Half Adder
a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Implementation tip
Can be built using two very elementary gates.
/** Computes the sum of two bits. */
CHIP HalfAdder {
IN a, b;
OUT sum, carry;
PARTS:
// Put your code here:
}
HalfAdder.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Full Adder
Implementation tips
Can be built using two
half-adders.
/** Computes the sum of three bits. */
CHIP HalfAdder {
IN a, b, c;
OUT sum, carry;
PARTS:
// Put your code here:
}
FullAdder.hdl
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
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
16-bit adder
Implementation tips
An n-bit adder can be built from n full-adder chips
The carry bit is “piped” from right to left
The MSB carry bit is ignored.
/*
* Adds two 16-bit, two’s-complement values.
* The most-significant carry bit is ignored.
*/
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put you code here:
}
Add16.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
16-bit incrementor
Implementation tip
The single-bit 0 and 1 values are represented in HDL as false and true.
/*
* Outputs in + 1.
* The most-significant carry bit is ignored.
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
// Put you code here:
}
Inc16.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
ALU
Implementation tips
Building blocks: Add16, and some gates built in project 1
Can be built with ~20 lines of HDL code
/** The ALU. */
// Manipulates the x and y inputs as follows:
// if (zx == 1) sets x = 0 // 16-bit true constant
// if (nx == 1) sets x = !x // bitwise Not
// if (zy == 1) sets y = 0 // 16-bit true constant
// if (ny == 1) sets y = !y // bitwise Not
// if (f == 1) sets out = x + y // int. 2's-complement addition
// if (f == 0) sets out = x & y // bitwise And
// if (no == 1) sets out = !out // bitwise Not
// if (out == 0) sets zr = 1 // 1-bit true constant
// if (out < 0) sets ng = 1 // 1-bit true constant
...
ALU.hdl
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Project 2 Resources
www.nand2tetris.org
All the necessary project 2 files are available in:
nand2tetris / projects / 02
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
More resources
HDL Survival Guide
Hardware Simulator Tutorial
nand2tetris Q&A forum
All available in: www.nand2tetris.org
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Best practice advice
Try to implement the chips in the given order
If you don’t implement some of the chips required in project 2, you can still use them as chip-parts in other chips. Just rename the given stub-files; this will cause the simulator to use the built-in versions of these chips
You can invent new, “helper chips”; however, this is not required: you can build any chip using previously-built chips only
Strive to use as few chip-parts as possible
You will have to use chips implemented in Project 1
For efficiency and consistency’s sake, use their built-in versions rather than your own implementation.
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Binary numbers
Binary addition
Negative numbers
Arithmetic Logic Unit
Project 2 overview
Chapter 2: Boolean arithmetic
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
Chapter 2
Boolean Arithmetic
From Nand to Tetris
Building a Modern Computer from First Principles
These slides support chapter 2 of the book
The Elements of Computing Systems
By Noam Nisan and Shimon Schocken
MIT Press
Nand to Tetris / www.nand2tetris.org / Chapter 2 / Copyright © Noam Nisan and Shimon Schocken Slide ‹#›
zx
no
zr
nx
zy
ny
f
ALU
ng
16 bits
16 bits
x
y
16 bits
out
/docProps/thumbnail.jpeg