Chapter 2: Bits, Data Types, and Operations

Bit & Bytes

Bit: Binary digits, two states (0 / 1) Byte: 8 bits

Data Types

Unary

n 1’s for number n. e.g. 11111 represents 5.

ASCII Codes

The way to transfer information between the computer and the keyboard.

48 0x30 --- '1'
65 0x41 --- 'A'
97 0x61 --- 'a'

Unsigned Integers

2’s Complement Integers

000 --- 0
001 --- 1
010 --- 2
011 --- 3
========== (An OVERFLOW if crossing this boundary)
100 --- -4
101 --- -3
110 --- -2
111 --- -1
(Note that the sum of the binary codes of two
complementary integers is 000)

How to quickly obtain -A: add 1 to the complement of A. i.e. -A = ~A + 1

Sign-EXTention: To extend the length of a representation, just extend the sign bit to the left.

Examining overflows: There is an overflow if and only if two positive numbers produce a negative sum, or two negative numbers produce a positive sum.

Bit Vectors

A collection of N bits that escribes states of N items. In LC-3, N = 16.

We can use logical operations & bit masks to modify a certain bit in the bit vector.

Logical Operations

Deal with logical variables (Booleans) and bit vectors.

NOT/COMPLEMENT/INVERT: NOT(0) = 1, NOT(1) = 0.

X	Y	ALL(X,Y) / X AND Y / XY	ANY(X,Y) / X OR Y / X+Y	X XOR Y
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

In LC-3, NOT and AND are in the ISA. OR can be operated with De Morgan’s Law:

OR(X,Y) = NOT(AND(NOT(X),NOT(Y)))

Bit masks

Can let us deal only with the bits we care about. For example, to clear the rightmost bit of a 6-bit vector and maintain the values of the other bits, AND it with the bit mask 111110. To set the rightmost bit of a 6-bit vector to 1, OR it with the bit mask 000001.

Floating point

(will not be used in LC-3)

Takes up 32(64/16) bits.

1	← e = 8(11/5) →	← 23(52/10) →
sign	exponent represents the range	fraction represents the position

N = (-1)^sign * 1.fraction * 2^{exponent-(2e-1+1)}

2^e-1+1 is called the excess code (the bias).

The fraction part won’t save the most significant bit, because it’s 1 for sure.

For example, to express 6.625, first convert it to normalised binary form:

6.625 = 1 * 2² + 1 * 2¹ + 1 * 2^-1 + 1 * 2^-3 = 110.101 = 1.10101000… * 2^129-127

So it can be coded:

0 10000001 10101000000000000000000

If the length of fraction part is not enough, the least significant bits will be rounded (rounded: lost due to limited space [truncated: lost due to limited time]).

Hexademical Notation