AP Computer Science Principles: Digital Information and Binary Representation Study Guide

Binary Number System and Base Conversions

• Converting Decimal Values to Binary:

  • Decimal $55$ Conversion:
  • To convert decimal $55$ to binary (base $2$), evaluate the highest powers of $2$ that sum to $55$:
    • $2^5 = 32$
    • $55 - 32 = 23$
    • $2^4 = 16$
    • $23 - 16 = 7$
    • $2^3 = 8$ (does not fit into $7$, binary digit is $0$
    • $2^2 = 4$
    • $7 - 4 = 3$
    • $2^1 = 2$
    • $3 - 2 = 1$
    • $2^0 = 1$
    • $1 - 1 = 0$
  • Combining these powers yields $32 + 16 + 0 + 4 + 2 + 1 = 55$, which corresponds to the binary sequence 110111.
  • Comparison of binary candidate options for decimal $55$:
    • 111011: Corresponds to $32 + 16 + 8 + 0 + 2 + 1 = 59$
    • 110111: Corresponds to $32 + 16 + 0 + 4 + 2 + 1 = 55$ (Correct representation)
    • 11011: Corresponds to $16 + 8 + 0 + 2 + 1 = 27$
    • 11111: Corresponds to $16 + 8 + 4 + 2 + 1 = 31$
  • Decimal $89$ Conversion:
  • To convert decimal $89$ to binary (base $2$), decompose $89$ into powers of $2$:
    • $2^6 = 64$
    • $89 - 64 = 25$
    • $2^5 = 32$ (does not fit into $25$, binary digit is $0$
    • $2^4 = 16$
    • $25 - 16 = 9$
    • $2^3 = 8$
    • $9 - 8 = 1$
    • $2^2 = 4$ (does not fit into $1$, binary digit is $0$
    • $2^1 = 2$ (does not fit into $1$, binary digit is $0$
    • $2^0 = 1$
    • $1 - 1 = 0$
  • Combining these values yields $64 + 0 + 16 + 8 + 0 + 0 + 1 = 89$, which corresponds to the binary sequence 1011001.
  • Comparison of binary candidate options for decimal $89$:
    • 101101: Corresponds to $32 + 0 + 8 + 4 + 0 + 1 = 45$
    • 11001101: Corresponds to $128 + 64 + 0 + 0 + 8 + 4 + 0 + 1 = 205$
    • 0101101: Corresponds to $32 + 0 + 8 + 4 + 0 + 1 = 45$
    • 1011001: Corresponds to $64 + 0 + 16 + 8 + 0 + 0 + 1 = 89$ (Correct representation)

• Ordering Numerical Values Across Different Bases:

  • To order a mixed list of binary and decimal numbers from least to greatest, convert all numbers to base $10$:
  • Binary 1100: $2^3 + 2^2 + 0 + 0 = 8 + 4 = 12$
  • Binary 1001: $2^3 + 0 + 0 + 2^0 = 8 + 1 = 9$
  • Decimal 6: $6$
  • Decimal 8: $8$
  • Numerical ordering from least to greatest:
  1. Decimal 6 (Value: $6$
  2. Decimal 8 (Value: $8$
  3. Binary 1001 (Value: $9$
  4. Binary 1100 (Value: $12$
  • Correct ordered sequence: Decimal 6, Decimal 8, Binary 1001, Binary 1100.

• Binary Sequences and Incremental Operations:

  • Incrementing Binary Sequences:
  • Binary sequences increase by $1$ through binary addition, adding $1$ to the least significant bit and carrying over as necessary.
  • Evaluation of $8$-bit binary sequences increasing by $1$ each step:
    • Sequence 0001 0110 ($22$), 0001 0111 ($23$), 0001 1000 ($24$): Increases by $1$ at each consecutive step (Correct).
    • Sequence 0001 0110 ($22$), 0001 0111 ($23$), 0001 1111 ($31$): Discontinuous jump from $23$ to $31$
    • Sequence 1010 1010 ($170$), 1010 1100 ($172$), 1010 1101 ($173$): Increments by $2$ on the first step.
    • Sequence 1011 1110 ($190$), 1011 1111 ($191$), 1010 0000 ($160$): Value decreases at the final step.
  • Identifying Missing Binary Values in Sequences:
  • Given a $5$-bit binary list representing sequential decimal values from $15$ to $18$:
    • Decimal $15$: 01111 ($8 + 4 + 2 + 1 = 15$
    • Decimal $16$: 10000 ($16$
    • Decimal $17$: 10001 ($16 + 1 = 17$
    • Decimal $18$: 10010 ($16 + 2 = 18$
  • The missing $5$-bit binary value corresponding to decimal $17$ in the list between 10000 and 10010 is 10001.

Bit Depth, Capacity, and Data Representation

• Fundamental Rules of Bit Capacity:

  • An $n$-bit binary system can represent exactly $2^n$ unique combinations or states.
  • The range of non-negative integers representable in $n$ bits extends from $0$ to $2^n - 1$.

• Scaling Bit Systems and System Upgrades:

  • Adding $1$ Bit to a Binary System:
  • Upgrading a system from $n$ bits to $n + 1$ bits multiplies the total number of unique representable items by $2$.
  • Mathematical ratio: $\frac{2^{n+1}}{2^n} = 2^1 = 2$
  • Example: A school upgrading ID storage from a $5$-bit system ($2^5 = 32$ total IDs) to a $6$-bit system ($2^6 = 64$ total IDs) allows $2$ times as many IDs to be added/stored overall.
  • Evaluating Fixed Bit Depth Margins:
  • A system storing multiple-choice test options using $4$ bits per option can represent up to $2^4 = 16$ unique options.
  • If a test expands the number of options per question from $4$ options to $8$ options, no increase in bits is required because $8 \le 16$. The fixed $4$-bit length remains fully sufficient.

• Determining Minimum Bit Depth Requirements:

  • Unique Staff ID Allocation:
  • Requirement: Assign unique ID numbers to $150$ staff members.
  • Calculation for required bits $n$:
    • $n = 7$ bits: $2^7 = 128$ unique IDs ($128 < 150$, insufficient)
    • $n = 8$ bits: $2^8 = 256$ unique IDs ($256 \ge 150$, sufficient)
  • Result: A minimum of $8$ bits is required to provide each of the $150$ workers a unique binary ID.
  • Character Set Encoding:
  • Requirement: Assign unique binary codes to $100$ distinct text characters.
  • Calculation for required bits $n$:
    • $n = 5$ bits: $2^5 = 32$ characters ($32 < 100$, insufficient)
    • $n = 6$ bits: $2^6 = 64$ characters ($64 < 100$, insufficient)
    • $n = 7$ bits: $2^7 = 128$ characters ($128 \ge 100$, sufficient)
  • Result: A minimum of $7$ bits is required to represent $100$ unique characters.

• Network Protocol Address Scaling (IPv4 vs. IPv6):

  • Internet Protocol version 4 (IPv4) utilizes $32$-bit binary addresses, providing $2^{32}$ unique addressable nodes.
  • Internet Protocol version 6 (IPv6) utilizes $128$-bit binary addresses, providing $2^{128}$ unique addressable nodes.
  • Quantitative expansion factor when upgrading from IPv4 to IPv6:
  • $\frac{2^{128}}{2^{32}} = 2^{128 - 32} = 2^{96}$
  • Upgrading from IPv4 to IPv6 yields $2^{96}$ times as many available IP addresses.

• Representation of Complex Media Types:

  • Binary sequences serve as the universal digital representation for all computer data.
  • Abstract media types representable by binary sequences include:
  • I. Sound (encoded by sampling analog audio waves at discrete intervals)
  • II. A String of Characters (encoded via fixed-length or variable-length bit patterns such as ASCII or Unicode)
  • III. Video (encoded as sequences of digital images and synchronized audio channels)
  • All three media types (I, II, and III) are represented using binary sequences.

Integer Representation Limits and Overflow Errors

• Mechanism of Overflow Errors:

  • Computer systems allocate a fixed number of bits to store integers.
  • An overflow error occurs when an arithmetic operation computes a value that exceeds the maximum numerical threshold representable within the fixed bit limit allocated for that variable.

• Quantitative Example of Arithmetic Overflow:

  • Environment: A programming language utilizes $3$ bits to store non-negative integers.
  • Maximum representable value: $2^3 - 1 = 7$
  • Attempted operation: A program attempts to add decimal values $3$ and $6$ and assign the result to variable num.
  • Step-by-step analysis:
  • Value $3$ in binary: 011 (fits in $3$ bits)
  • Value $6$ in binary: 110 (fits in $3$ bits)
  • Computed sum: $3 + 6 = 9$
  • Value $9$ in binary: 1001 (requires $4$ bits)
  • Result: An overflow error occurs because the sum $9$ cannot be represented using $3$ bits ($9 > 7$).

• Distinguishing Overflow Errors from Round-off Errors:

  • Overflow Error: Triggered when an integer calculation yields a magnitude greater than the maximum allowable value for a fixed bit width.
  • Round-off Error: Triggered when fractional or floating-point numbers cannot be stored with exact precision due to bit limits, leading to approximate representations.