Bitwise operations, IEEE 754 floating point and ASCII

On the previous page you read bits as integers. This page has three new things: logic operations on bits (masks), IEEE 754 for numbers with fractions, and ASCII for characters. All three are solved with a recipe. Whoever knows the recipe gets full marks.

Logic operations (bitwise operations)

These operations are done separately on the bits in the same position of two numbers. There is no carry, the bits do not affect each other.

       1100 1001   (0xC9)
AND    1111 0000   (0xF0)
       ---------
       1100 0000   (0xC0)     the low 4 bits were cleared

Bit mask

The second number chosen to change or read some bits of a number is called a mask. Which operation you choose depends on what you want to do:

A way to remember: with AND, 0 kills; with OR, 1 creates; with XOR, 1 flips. In AND the places where the mask is 1, and in OR and XOR the places where it is 0, leave the number untouched.

TIP · Bit numbers. Bits are numbered from the right, starting at 0. The mask of bit $k$ is $2^k$: bit 0 = 0x01, bit 3 = 0x08, bit 4 = 0x10, bit 5 = 0x20, bit 7 = 0x80.

The LC-3 has only AND and NOT (week 7). You build OR with DeMorgan: $A \text{ OR } B = \text{NOT}(\text{NOT }A \text{ AND NOT }B)$.

Numbers with fractions: IEEE 754

Integer representations cannot write 3.75 or $6 \times 10^{23}$. For this the binary form of scientific notation is used: $\pm 1.xxx \times 2^{e}$. IEEE 754 single precision (float in C) consists of 32 bits:

$N = (-1)^S \times 1.\text{fraction} \times 2^{\,\text{exponent} - 127} \qquad (1 \le \text{exponent} \le 254)$

The leading 1 is the same in every normalized number, so it is not written (hidden bit). This way 24 bits of precision fit in 23 bits. The exponent is stored shifted by 127 (biased) so that negative powers can be written too.

Special cases:

Converting the fractional part to binary

Multiply the fraction by 2, write the integer part (0 or 1), and continue with the fractional part. Stop when the fraction is 0. The bits you wrote are read from top to bottom.

0.375 × 2 = 0.75   → 0
0.75  × 2 = 1.5    → 1
0.5   × 2 = 1.0    → 1   (stop)
0.375 = 0.011

Encode recipe (number → bits)

Worked example: 6.125

1) sign: positive → S = 0
2) 6 = 110
3) 0.125: ×2=0.25→0, ×2=0.5→0, ×2=1.0→1  → .001
   6.125 = 110.001
4) normalize: 110.001 = 1.10001 × 2^2   (point moves 2 to the left)
5) exponent = 2 + 127 = 129 = 1000 0001
6) fraction = 10001 and 18 zeros
7) 0 10000001 10001000000000000000000
   0100 0000 1100 0100 0000 0000 0000 0000 = 0x40C40000

Worked example: -2.5

2.5 = 10.1 = 1.01 × 2^1
S = 1, exponent = 128 = 1000 0000, fraction = 01000...
1 10000000 01000000000000000000000 = 1100 0000 0010 0000 ... = 0xC0200000

Decode recipe (bits → number)

Worked example: 0x41F40000

1) 0100 0001 1111 0100 0000 0000 0000 0000
2) S = 0 | exponent = 1000 0011 | fraction = 1110100...
3) exponent = 131 → e = 131 - 127 = 4
4) significand = 1.11101
5) 1.11101 × 2^4 = 11110.1   (point moves 4 to the right)
6) 11110 = 30, .1 = 0.5 → 30.5

Worked example: 0xC1100000

1100 0001 0001 0000 ... → S = 1 | exponent = 1000 0010 = 130 → e = 3 | fraction = 001...
1.001 × 2^3 = 1001 = 9 → -9

PITFALL · field boundaries do not line up with hex digits. The first bit of 0x41 is S, the next 7 bits are the start of the exponent; the last bit of the exponent is the first bit of the next hex digit. First write the 32 bits on one line, then draw the split as 1 | 8 | 23.

PITFALL · four mistakes that lose points in IEEE. (1) Forgetting to add or subtract 127. (2) Writing the hidden 1 into the fraction. (3) Filling the fraction from the right: the bits start right after the point, and the rest is padded with 0 on the right. (4) When converting to hex, keeping S separate and breaking the grouping in fours.

Not every decimal number can be written exactly

The binary expansion of 0.1 repeats forever (0.0001100110011…). Because it does not fit in 23 bits, it is rounded. In C, comparisons like 0.1f + 0.2f == 0.3f are dangerous for this reason. Fractions whose denominator is a power of 2 (1/2, 3/8, 5/16) are written exactly.

ASCII: characters

Every character that comes from the keyboard or goes to the screen is a number. ASCII (American Standard Code for Information Interchange) maps each character to an 8-bit code (actually 7 bits are enough, the top bit is 0).

Two properties you need to know:

1. Value of a digit = code - x30. ‘7’ = x37 → 7. The reverse: 3 + x30 = x33 = ‘3’.
2. Upper and lower case letters differ only in bit 5 (x20 = 32). ‘M’ = x4D = 0100 1101, ‘m’ = x6D = 0110 1101.

The word “CAT” sits in memory as x43 x41 x54. In the LC-3, a string written with .STRINGZ puts each character in one word (16 bits) and adds x0000 at the end (week 10).

Common mistakes