Number Systems and Encoding
1. Positional Number Systems
Basic Concepts
Positional number system: a method of counting that follows the carry principle
Radix (base): the number of distinct digits that may be used in each position
Place value (positional weight): the magnitude that the digit in a given position represents
Common Number Systems
Binary:
- Radix: 2
- Digits: 0, 1
- Place value: 2^n
- Application: the internal representation in a computer
Octal:
- Radix: 8
- Digits: 0-7
- Place value: 8^n
- Application: program debugging
Decimal:
- Radix: 10
- Digits: 0-9
- Place value: 10^n
- Application: everyday arithmetic
Hexadecimal:
- Radix: 16
- Digits: 0-9, A-F
- Place value: 16^n
- Application: program development
Converting Between Number Systems
Decimal to another base:
- Integer part: repeated division by the base, collecting the remainders
- Fractional part: repeated multiplication by the base, collecting the integer digits
Another base to decimal:
- Expand by place value and sum the terms
Binary and octal:
- Three binary digits correspond to one octal digit
Binary and hexadecimal:
- Four binary digits correspond to one hexadecimal digit
2. True Values and Machine Numbers
Basic Concepts
True value: the real value of a number, carrying a sign
Machine number: the representation of a number inside a computer, with a fixed number of bits
Sign-Magnitude Representation
Definition: a sign bit plus the value bits
Characteristics:
- Sign bit: 0 for positive, 1 for negative
- Value bits: the same as the magnitude of the true value
- Zero has two representations: +0 and -0
Range of representation:
- An n-bit sign-magnitude number: from -(2^(n-1)-1) to +(2^(n-1)-1)
Ones’ Complement Representation
Definition: positive numbers are the same as in sign-magnitude; for negative numbers the sign bit is kept and the value bits are inverted
Characteristics:
- Positive numbers: the same as sign-magnitude
- Negative numbers: the sign bit is 1 and the value bits are inverted
- Zero has two representations: +0 and -0
Range of representation:
- An n-bit ones’ complement number: from -(2^(n-1)-1) to +(2^(n-1)-1)
Two’s Complement Representation
Definition: positive numbers are the same as in sign-magnitude; for negative numbers the sign bit is kept and the value bits are inverted and then incremented by 1
Characteristics:
- Positive numbers: the same as sign-magnitude
- Negative numbers: the sign bit is 1 and the value bits are inverted and incremented
- Zero has only one representation: +0
Range of representation:
- An n-bit two’s complement number: from -2^(n-1) to +(2^(n-1)-1)
3. Character and String Encoding
ASCII Encoding
Basic ASCII:
- 7-bit encoding
- 128 characters
- 0-31: control characters
- 32-126: printable characters
Extended ASCII:
- 8-bit encoding
- 256 characters
- 128-255: extended characters
Unicode Encoding
Basic concepts:
- A unified character encoding standard
- Supports characters from many languages
- Backwards compatible with ASCII
Encoding forms:
- UTF-8: a variable-length encoding of 1-4 bytes
- UTF-16: a 16-bit or 32-bit encoding
- UTF-32: a fixed-length 32-bit encoding
Characteristics:
- Supports every language in the world
- One unified encoding standard
- In very wide use
Chinese Character Encoding
GB2312:
- The national standard code
- A double-byte encoding
- Supports simplified Chinese
GBK:
- An extension of the national standard code
- Compatible with GB2312
- Supports traditional Chinese
GB18030:
- The newest national standard
- Supports the scripts of ethnic minorities
- Compatible with Unicode
Exercise 1
Represent the decimal number -25 as an 8-bit sign-magnitude, ones’ complement, and two’s complement number.
Approach: Convert the magnitude 25 into binary, then apply each encoding rule in turn — invert the value bits for ones’ complement, and invert plus increment for two’s complement.
Steps:
- Sign-magnitude:
- Sign bit: 1 (negative)
- Value bits: the binary representation of 25
- 25 = 16 + 8 + 1 = 11001
- Sign-magnitude: 10011001
- Ones’ complement:
- Sign bit: 1 (negative)
- Value bits: 11001 inverted = 00110
- Ones’ complement: 11100110
- Two’s complement:
- Sign bit: 1 (negative)
- Value bits: the ones’ complement plus 1
- 00110 + 1 = 00111
- Two’s complement: 11100111
Answer: The 8-bit sign-magnitude form of -25 is 10011001, the ones’ complement form is 11100110, and the two’s complement form is 11100111.
Exercise 2
Briefly state the differences between sign-magnitude, ones’ complement, and two’s complement.
Approach: Compare the three encodings on the same four axes — how the sign is stored, how the value bits are built, how zero is represented, and how suitable the encoding is for arithmetic.
Steps:
- Sign-magnitude:
- A sign bit plus the value bits
- Positive and negative numbers are symmetric
- Zero has two representations
- Unsuitable for arithmetic
- Ones’ complement:
- Positive numbers are the same as sign-magnitude
- For negative numbers the value bits are inverted
- Zero has two representations
- The arithmetic is complicated
- Two’s complement:
- Positive numbers are the same as sign-magnitude
- For negative numbers the value bits are inverted and incremented
- Zero has only one representation
- Suits arithmetic and is in universal use
Answer: Sign-magnitude stores a sign bit beside the magnitude and has two zeros; ones’ complement inverts the value bits of a negative number and still has two zeros; two’s complement inverts and increments a negative number and has a single zero, which is why it is the representation of choice for arithmetic.
| Term | Abbreviation | Explanation |
|---|---|---|
| Binary | - | A positional system with radix 2 |
| Octal | - | A positional system with radix 8 |
| Decimal | - | A positional system with radix 10 |
| Hexadecimal | Hex | A positional system with radix 16 |
| Sign-magnitude | - | A sign bit plus the magnitude |
| Ones’ complement | - | Negative numbers are inverted bit by bit |
| Two’s complement | - | Negative numbers are inverted and then incremented |
| Offset binary | - | The stored value has a fixed offset added to it |
| Fixed-point number | - | The radix point has a fixed position |
| Floating-point number | - | The radix point moves with the exponent |
| Exponent | - | The exponent field of a floating-point number |
| Mantissa | - | The significand field of a floating-point number |
| Normalization | - | The standard form of a floating-point number |
| Overflow | - | The result falls outside the representable range |
| Underflow | - | The result is too small to be represented |
| Machine zero | - | The bit pattern a floating-point unit uses for zero |
| Binary coded decimal | BCD | Decimal digits stored in binary |
| American Standard Code for Information Interchange | ASCII | The standard character encoding |
| Chinese character encoding | - | The encoding of Chinese characters |