1.1Numeric representation & information theory

A computer represents all data internally as binary (a sequence of 0s and 1s). Whether you are reading and writing pseudocode for Exam B or discussing performance and error for Exam A, you first need a solid grasp of how numbers are represented and where errors creep in. Rather than rote memorization, this section digs into numeric representation from the angle of why each representation is used in practice.

1.1.1Binary, hexadecimal, and base conversion

• Binary is a number system using only 0 and 1. Because computer circuits operate in two states (on/off), binary is the fundamental internal representation.
• Hexadecimal uses 16 symbols (0-9 and A-F). Because 4 binary digits map exactly to 1 hex digit, hex serves as a human-readable compressed notation for binary and is widely used for memory addresses, color codes, and the like.
• A practical conversion tip: for binary to hex, group digits by 4 starting from the least-significant bit and convert each group to one hex digit. Example: 1011 1100 -> B C -> 0xBC. Decimal <-> binary conversion uses repeated division/remainder (decimal to binary) or positional weighting (binary to decimal).

1.1.2Representing negative numbers with complements

• A complement expresses a number as the difference from a reference value. Computers represent negative numbers using complements so that subtraction can be carried out with addition circuitry alone.
• In binary, the two's complement is the standard. To compute it: flip every bit (the one's complement) and then add 1. Example (8 bits): 5 = 00000101; its one's complement is 11111010; its two's complement (-5) = 11111011.
• A benefit of two's complement: 0 has exactly one representation, and the same addition circuit handles subtraction. An n-bit two's complement value ranges from -2^(n-1) to 2^(n-1)-1.

1.1.3Floating-point numbers and error

• A floating-point number represents a real number as a triple of sign, exponent, and mantissa (IEEE 754 is the representative standard). It approximates a wide range of values in a limited number of bits, but cannot represent every real number exactly.
• Rounding error arises when digits that cannot be represented are dropped (e.g., via rounding). Cancellation (loss of significance) is the sharp drop in significant digits that occurs when subtracting two nearly equal values. Loss of trailing digits occurs when adding/subtracting values of very different magnitudes, causing the smaller value to be rounded away.

Consider a batch job in an accounting system that computes "the difference between two nearly equal, large sales amounts." A developer implements this difference using a floating-point type and gets a result that is slightly off from the expected figure. This is very likely cancellation (loss of significance): subtracting two values whose magnitudes are nearly equal cancels out the leading digits, sharply reducing the number of significant digits, so the rounding error in the trailing digits is relatively amplified and becomes visible. The fix is a design decision: handle values that need exact precision—like money—as integers (in the smallest unit, e.g. yen or cents) or fixed-point numbers instead of floating point, or reorder the calculation to avoid the cancellation-prone step. Now consider negative-number representation: to get -5 as an 8-bit signed integer, flip each bit of 5 (00000101) to get 11111010 (the one's complement), then add 1 to get 11111011 (the two's complement) as the representation of -5. As a check, adding 00000101 + 11111011 in binary, and discarding the carry out of the 9th bit, gives 00000000, confirming 5 + (-5) = 0 holds correctly. Complement notation exists to satisfy the practical need of "implementing subtraction with addition-only hardware," while floating-point error is an inevitable consequence of the constraint of "approximating infinitely many real numbers with a finite number of bits."

1.1.4Information content and encoding

• Information content quantifies the "degree of surprise" upon learning that an event occurred. A less probable event carries more information. The unit is the bit, computed as log2(1/p) where p is the probability of the event.
• Example: an event with two equally likely outcomes (a coin flip) carries log2(1/0.5) = 1 bit of information. With 8 equally likely outcomes, it is log2(8) = 3 bits—more possible outcomes (more surprise) means more information.
• Encoding converts information into another form such as a bit string. Character codes (e.g., Unicode/UTF-8) and compression codes (e.g., Huffman coding, which assigns shorter codes to more frequent symbols) are representative examples.

1.1.5Section summary

• Two's complement = flip bits, then add 1. It lets subtraction be implemented with addition circuitry alone
• Floating-point errors: distinguish rounding error / cancellation (subtracting near-equal values) / loss of trailing digits (mixing very different magnitudes)
• Information content = log2(1/p) bits (less probable events carry more). Encoding converts that information into a bit string or similar form