• Bit-width intuition (Basic)
• Bit-width and misinterpretation (Basic)
• Modular arithmetic and 2’s complement representation (Basic)
• Another Base Conversion (Basic)
• Representing -32 on different number systems (Basic)
• Byte and Memory Intuition (Intermediate)
• Hex + 2’s Complement (Intermediate)
• From logic to decision (Intermediate)
• Proof of 2’s Complement (Challenging)

50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Basics of Information

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

Bit-width intuition (Basic)

You are designing a small digital device that needs to represent three different states: IDLE, RUN, and ERROR. 1. What is the minimum number of bits required to represent these three states?

2. Write down all binary patterns available using that number of bits.

3. How many of those patterns are unused?

4. Which binary pattern must be mapped to each of the states (IDLE, RUN, ERROR)?

Bit-width and misinterpretation (Basic)

You observe the bit pattern:

1001

(a) Interpret the value in unsigned 4-bit representation.

(b) Interpret the value in signed 4-bit 2’s complement.

(c) Now assume the same pattern is widened to 8 bits using sign extension, that is to keep the value mathematically consistent (as per what you wrote in part b) despite having wider bits. Write the full 8-bit pattern and give the decimal value.

Modular arithmetic and 2’s complement representation (Basic)

Most computers choose a particular word length (measured in bits) for representing integers and provide hardware that performs various arithmetic operations on word-size operands. The current generation of processors have word lengths of 32 bits; restricting the size of the operands and the result to a single word means that the arithmetic operations are actually performing arithmetic modulo \(2^{32}\).

Almost all computers use a 2’s complement representation for integers since the 2’s complement addition operation is the same for both positive and negative numbers. In 2’s complement notation, one negates a number by forming the 1’s complement (i.e: for each bit, changing 0 to a 1 and vice versa) representation of the number and then adding 1. By convention, we write 2’s complement integers with the most-significant bit (MSB) on the left and the least-significant bit (LSB) on the right. Also, by convention, if the MSB is 1, the number is negative, otherwise it’s non-negative.

(a.) How many different values can be encoded in a 32-bit word?

(b.) Please use a 32-bit 2’s complement representation (signed bits) to answer the following questions. What are the representations for:

1. Zero
2. The most positive integer that can be represented
3. The most negative integer that can be represented

(c.) What are the decimal values for the most positive and the most negative number that can be represented by this signed 32-bit machine?

(d.) Since writing a string of 32 bits gets tedious, it’s often convenient to use hexadecimal representation where a single digit in the range of 0-9 or A-F is used to represent groups of 4 bits. Give the 8-digit hexadecimal equivalent of the following decimal and binary numbers:

1. Base 10: \(37_{10}\)
2. Base 10: \(-32768_{10}\)
3. Base 2: 1101 1110 1010 1101 1011 1110 1110 1111

(e). Calculate the following using 6-bit 2’s complement arithmetic (which is just a fancy way of saying to do ordinary addition in base 2, keeping only 6 bits of your answer). Show your work using binary notation. Remember that subtraction can be performed by negating the second operand and then adding to the first operand.

1. 13 + 10
2. 15 - 18
3. 27 - 6

Another Base Conversion (Basic)

Consider an 8-bit signed number systems. Do the following base conversion, and indicate with a 0b prefix for binary systems and 0x prefix for hexadecimal systems. Octal and decimal systems do not have prefixes.

1. 76 (decimal) to binary
2. 0b10000001 (binary) to decimal
3. 0b10011101 (binary) to hexadecimal
4. 0xBF (hexadecimal) to binary
5. 0xC6 (hexadecimal) to octal

Representing -32 on different number systems (Basic)

Which of the following signed numbers is the representation of number -32 for either an 8-bit or 16-bit system? Note: the answer must be either 8-bit or 16-bit long.

1. 0b1010 0000
2. 0b1110 0000
3. 0b0001 0000
4. 0xE0
5. 0x80E0
6. 0xFFE0
7. 0x10E0
8. 0x800000E0
9. 0xFFFFFFE0

Byte and Memory Intuition (Intermediate)

A simple system has a memory of 256 bytes.

(a.) How many bits is this in total?

(b.) If you want to uniquely refer to (or “label”) every byte in this memory using a binary number, what is the minimum number of bits required for these labels?

(c.) If each memory location stores a 16-bit value, how many different values can a single location represent?

Hex + 2’s Complement (Intermediate)

Find the 8-bit signed decimal value of:

0xD6

Show your working in binary.

From logic to decision (Intermediate)

Let two 2-bit numbers A and B be given:

• A = A1A0
• B = B1B0

You must determine if A > B using logic gates only. We are only testing for A > B, not B < A or B == A.

(a.) Write the Boolean expression for the output Z = 1 if A > B using any logic gate.

(c.) Identify which part of the expression corresponds to the MSB comparison and which to the LSB comparison.

Proof of 2’s Complement (Challenging)

At first glance, “Complement and add 1” doesn’t seem like an obvious way to negate a two’s complement number. By manipulating the expression \(A + (-A) = 0\), show that “complement and add 1” does produce correct representation for the negative of a two’s complement number.

Hint: express 0 as (-1 + 1) and rearrange the terms to get -A on one side and ZZZ+1 on the other and then think about how the expression ZZZ is related to A using only logical operations (AND, OR, NOT).

Also, see how binary subtraction ‘borrow’ method works here if you dont know how it works.

Video Explanation here.