CS274: Computer Architecture - Number Systems

Activity Goals

The goals of this activity are:
  1. To convert between decimal, hexadecimal, and binary number representations
  2. To explain why computers represent values in binary rather than in another number system

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Converting From Decimal to Binary

Divide the value by 2, and append the remainder to the beginning of your output string. Repeat using the new quotient until the quotient is 0.

Number Quotient / 2 Remainder
375 187 1
187 93 1
93 46 1
46 23 0
23 11 1
11 5 1
5 2 1
2 1 0
1 0 1

Questions

  1. Using the procedure above, convert 1024 to binary.
  2. Convert 617 to binary.
  3. Why might a computer prefer to store values in binary rather than in another number system?

Model 2: Converting From Binary to Decimal

Multiply the digit (1 or 0) by its place value (2 to the power of the digit position, right to left, beginning at the 1 place), and add up the result.
In the example in the table below: 00001011001 = 1 * 1 + 0 * 2 + 0 * 4 + 1 * 8 + 1 * 16 + 0 * 32 + 1 * 64 + 0 * 128 + 0 ... = 1 + 8 + 16 + 64 = 89

Place Value 1024 512 256 128 64 32 16 8 4 2 1
0 0 0 0 1 0 1 1 0 0 1

Questions

  1. Convert 0b1000100001 from binary to decimal.
  2. Convert 0b10001001 from binary to decimal.
  3. Convert 0b101110111 from binary to decimal.

Model 3: Converting From Binary to Hexadecimal

Take each group of 4 binary values from left to right. Look them up in the table to obtain the corresponding hexadecimal digit, and output that digit.

Positionalnotationtable

Questions

  1. What is the ASCII value of the letter C and the letter K? What are these values in binary, decimal, and hexadecimal?
  2. Suppose a binary value is fewer than 4 bits, like 0b110. How can you convert this to a 4-bit binary value so that it can be looked up in the table?
  3. Convert 0b1000100001 from binary to hexadecimal.
  4. Convert 0b10001001 from binary to hexadecimal.
  5. Convert 0b101110111 from binary to hexadecimal.
  6. Convert 375 from decimal to binary, and then to hexadecimal.

Model 4: Converting From Hexadecimal to Binary

Using the binary to hexadecimal table, look up the binary representation for each hexadecimal digit. In other words, convert each hexadecimal digit to decimal, and then to binary. This will result in a four digit binary number. Output those binary bits. Repeat for each hexadecimal digit from left to right.

Questions

  1. Convert 0xCAFE from hexadecimal to binary.
  2. Convert 0x3C from hexadecimal to binary, and from binary to decimal.
  3. Convert 0xFF from hexadecimal to binary, and from binary to decimal.

Model 5: Practice Warm-Up: Extracting Bits with Shifts and Masks

Now that you can convert between binary and hexadecimal, you can pull individual bits out of a value! To extract a field of bits from an integer, shift the value to the right so that the field you want begins at bit position 0, and then AND the result with a "mask" of ones that is exactly as wide as the field. The AND keeps only the bits where the mask is 1, and zeroes out everything else.

In general, to extract bits k down to j (inclusive) of a value x, compute: (x >> j) & ((1 << (k - j + 1)) - 1)

Field Width (bits) Mask Arithmetic Mask (binary) Mask (hex)
1(1 << 1) - 1 = 2 - 1 = 110x1
2(1 << 2) - 1 = 4 - 1 = 3110x3
3(1 << 3) - 1 = 8 - 1 = 71110x7
4(1 << 4) - 1 = 16 - 1 = 1511110xF
8(1 << 8) - 1 = 256 - 1 = 255111111110xFF

Worked Mini-Example 1: extract bits 3..2 of 220
  1. Write 220 in binary: 220 = 1101 1100.
  2. The field is 2 bits wide (bits 3 and 2), so the mask is (1 << 2) - 1 = 4 - 1 = 3 = 0b11.
  3. Shift right by j = 2: 1101 1100 >> 2 = 0011 0111 (the two rightmost bits fall off, and bits 3..2 land in positions 1..0).
  4. AND with the mask: 0011 0111 & 0000 0011 = 0000 0011 = 3.
  5. Check against step 1: bits 3..2 of 1101 1100 are indeed 11 = 3.
Worked Mini-Example 2: extract bits 7..4 (the high nibble) of 0xAB
  1. Write 0xAB in binary: 1010 1011.
  2. The field is 4 bits wide, so the mask is (1 << 4) - 1 = 16 - 1 = 15 = 0xF.
  3. Shift right by 4: 1010 1011 >> 4 = 0000 1010 = 0xA.
  4. AND with the mask: 0000 1010 & 0000 1111 = 0000 1010 = 0xA = 10. Notice that this extracts the first hexadecimal digit - each hex digit is a 4-bit field!
Worked Mini-Example 3: extract bit 0 of 41
  1. Write 41 in binary: 0010 1001.
  2. A 1-bit field needs no shift when j = 0, and the mask is (1 << 1) - 1 = 1.
  3. 0010 1001 & 0000 0001 = 1: bit 0 is 1, which tells us 41 is odd!

Practice Problems
  1. Extract bits 5..3 of 231 (0xE7).
    Solution 231 = 1110 0111. Shift right by 3: 1110 0111 >> 3 = 0001 1100 = 28. Mask for a 3-bit field: (1 << 3) - 1 = 7. 28 & 7 = 0001 1100 & 0000 0111 = 100 = 4.
  2. Extract bits 11..8 of 0xBEEF.
    Solution Shift right by 8: 0xBEEF >> 8 = 0xBE. Mask for a 4-bit field: 0xF. 0xBE & 0xF = 0xE = 14. (Shortcut: bits 11..8 are exactly the third hex digit from the right, which is E.)
  3. Write an expression that extracts bits 6..4 of a variable x, and evaluate it for x = 0x5C.
    Solution The expression is (x >> 4) & 0x7 (a 3-bit mask). 0x5C = 0101 1100. 0101 1100 >> 4 = 0000 0101 = 5, and 5 & 7 = 5 = 0b101.

Questions

  1. Why must you shift before applying the mask (what would x & 0b11 give you if the field you wanted was in bits 3..2)?
  2. What mask (in hex) would you use to extract an 8-bit field? A 16-bit field?

Model 6: Practice: Bitwise Operators and Network Addresses

Bit masks are not just an academic exercise - your computer uses them every time it sends a network packet! An IPv4 address like 192.168.1.12 is really just a 32-bit binary number: each of the four numbers (called "octets") is one byte, written in decimal and separated by dots. The "slash" suffix in 192.168.1.12/24 is called CIDR notation, and it says that the first 24 bits identify the network, while the remaining 32 - 24 = 8 bits identify the host on that network.

The netmask for a /24 network is 24 ones followed by 8 zeros: 11111111 11111111 11111111 00000000 = 255.255.255.0 = 0xFFFFFF00. ANDing an address with its netmask keeps the network part and zeroes out the host part.

Computing the mask from the prefix length: for a prefix length n, the mask is 0xFFFFFFFF << (32 - n). For n = 24:
  1. 32 - n = 32 - 24 = 8.
  2. 0xFFFFFFFF << 8 shifts all 32 ones left by 8 positions; the top 8 ones fall off the left end, and 8 zeros shift in on the right.
  3. The result is 0xFFFFFF00 = 11111111 11111111 11111111 00000000 = 255.255.255.0.

Worked Example: what network is 192.168.1.12/24 on?
  1. Convert each octet to 8-bit binary: 192 = 11000000, 168 = 10101000, 1 = 00000001, 12 = 00001100.
  2. Write the /24 mask underneath and AND each column (1 AND x = x; 0 AND x = 0):
Address: 192.168.1.12    11000000 . 10101000 . 00000001 . 00001100
Mask:    255.255.255.0   11111111 . 11111111 . 11111111 . 00000000
AND      =========================================================
Network: 192.168.1.0     11000000 . 10101000 . 00000001 . 00000000
  1. The network address is 11000000.10101000.00000001.00000000 = 192.168.1.0.
  2. The host part is the last 8 bits of the original address: 00001100 = 12. So this is host number 12 on network 192.168.1.0.

Practice Problems
  1. What is the netmask for a /8 network, in dotted-quad, binary, and hex? What is the network address of 10.1.2.3/8?
    Solution A /8 mask is 8 ones then 24 zeros: 11111111 00000000 00000000 00000000 = 255.0.0.0 = 0xFF000000. ANDing keeps only the first octet: the network is 10.0.0.0, and the host part is 1.2.3 (bits 00000001 00000010 00000011).
  2. Compute the mask for a /26 network, and find the network address of 172.16.5.130/26.
    Solution 0xFFFFFFFF << (32 - 26) = 0xFFFFFFFF << 6 = 0xFFFFFFC0: 26 ones then 6 zeros, or 255.255.255.192 (since 11000000 = 192). The first three octets are fully masked, so only the last octet changes: 130 = 10000010, and 10000010 AND 11000000 = 10000000 = 128. The network is 172.16.5.128, and the host part is 000010 = 2.
  3. Now a mask that does not fall on an octet boundary: find the mask for /20, and the network address of 192.168.37.44/20.
    Solution 0xFFFFFFFF << (32 - 20) = 0xFFFFFFFF << 12 = 0xFFFFF000, which is 11111111 11111111 11110000 00000000 = 255.255.240.0 (since 11110000 = 240). The mask splits the third octet: 37 = 00100101, and 00100101 AND 11110000 = 00100000 = 32. The network is 192.168.32.0. The 12 host bits are 0101 00101100, i.e. host number 5 * 256 + 44 = 1324.
  4. Are the hosts 192.168.1.77 and 192.168.2.80 on the same /24 network? Are they on the same /16 network? (Two hosts are on the same network exactly when address1 AND mask == address2 AND mask.)
    Solution With a /24 mask: 192.168.1.77 AND 255.255.255.0 = 192.168.1.0, but 192.168.2.80 AND 255.255.255.0 = 192.168.2.0. These differ, so they are not on the same /24 network. With a /16 mask (255.255.0.0), both AND to 192.168.0.0, so they are on the same /16 network.
  5. How many host bits does a /30 network have, and how many distinct addresses can it hold?
    Solution 32 - 30 = 2 host bits, giving 2^2 = 4 addresses (in practice, the all-zeros host is the network address and the all-ones host is the broadcast address, leaving 2 usable hosts). The mask is 0xFFFFFFFF << 2 = 0xFFFFFFFC = 255.255.255.252.

Common Pitfalls
  • Forgetting that the dots are cosmetic: an IPv4 address is one 32-bit number; convert each octet to 8 bits (padding with leading zeros, e.g. 1 = 00000001) before masking.
  • Shifting by n instead of 32 - n when computing the mask from the prefix length: /24 means shift left by 8, not by 24.
  • Assuming masks always end on an octet boundary: for prefixes like /20 or /26, one octet is split, so you must convert that octet to binary to AND it correctly.
  • Confusing the network AND with the host part: the host part is what the mask zeroes out; you can extract it with address & ~mask (AND with the inverted mask).

Questions

  1. Why is AND the right operator for extracting the network address, rather than OR or XOR?
  2. Your home router probably uses 192.168.0.0/16 addresses. How many host bits (and therefore how many possible devices) is that?

Model 7: Key Formulas and Concepts Recap

A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!

Key Rules and Formulas
  • Decimal to binary: repeatedly divide by 2 and prepend the remainder, until the quotient is 0. Micro-example: 13 / 2 = 6 r 1; 6 / 2 = 3 r 0; 3 / 2 = 1 r 1; 1 / 2 = 0 r 1; reading the remainders backwards gives 1101.
  • Binary to decimal: multiply each digit by its place value (1, 2, 4, 8, ... from the right) and add. Micro-example: 1101 = 1*8 + 1*4 + 0*2 + 1*1 = 13.
  • Binary to hexadecimal: group bits into 4s from the right and look each group up (0000=0 ... 1001=9, 1010=A ... 1111=F). Micro-example: 1101 0111 = 0xD7.
  • Hexadecimal to binary: expand each hex digit to exactly 4 bits. Micro-example: 0x3C = 0011 1100.
  • Extract bits k..j: (x >> j) & ((1 << (k - j + 1)) - 1). Micro-example: bits 3..2 of 220 = (220 >> 2) & 3 = 55 & 3 = 3.
  • Netmask from prefix /n: 0xFFFFFFFF << (32 - n); network address = address AND mask. Micro-example: /24 gives 0xFFFFFF00 = 255.255.255.0, and 192.168.1.12 AND 255.255.255.0 = 192.168.1.0.
  • n bits hold 2^n values: 8 bits hold 256 values (0..255); 10 bits hold 1024.

Place values:   128   64   32   16    8    4    2    1
220        =      1    1    0    1    1    1    0    0
                128 + 64      + 16 +  8 +  4          = 220

Glossary
TermMeaning
BitA single binary digit, 0 or 1
Nibble4 bits; exactly one hexadecimal digit
Byte (octet)8 bits; holds values 0..255
Base (radix)The number of distinct digits in a number system (2 for binary, 10 for decimal, 16 for hex)
Place valueThe weight of a digit position: base^position, counting from 0 at the right
Most significant bit (MSB)The leftmost (highest place value) bit
Least significant bit (LSB)The rightmost (ones place) bit
BitmaskA value ANDed with another to keep only certain bits
CIDR prefix (/n)The number of leading 1 bits in a netmask; the first n bits of an IPv4 address name the network
NetmaskThe 32-bit mask of n ones then (32-n) zeros used to separate network bits from host bits

Questions

  1. Without looking, convert 45 to binary and to hexadecimal, then check yourself using the recap rules.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.