I. In-Class Exercises

Programming Exercises

1. Binary to Decimal: L2111
2. Decimal to Binary: L2112
3. Base Conversion: L2113

II. Knowledge Summary

✨ Core Concept of Number Base Conversion

A numeral system is a set of symbolic rules for representing and processing numbers, including digit symbols and counting rules. Different civilizations and use cases have developed different numeral systems.

✨ Digit Symbols in Numeral Systems

There are many types of digit symbols. Mathematics and computer science commonly use Arabic numerals for counting.

Other common digit symbols include:

• Arabic numerals: 1, 2, 3, 4, 5, ...
• Chinese numerals: one, two, three, four, five, ...
• Roman numerals: I, II, III, IV, V, ...

✨ Positional Notation

Positional notation is the most commonly used counting rule in daily life. Base-n means using n different digit symbols to count, carrying over when reaching n.

Common bases include:

• Decimal (base 10): Uses digits 0-9, carries at 10
• Binary (base 2): Uses digits 0-1, carries at 2
• Octal (base 8): Uses digits 0-7, carries at 8
• Hexadecimal (base 16): Uses digits 0-9 and A, B, C, D, E, F, carries at 16

In addition, many unit conversions also use the concept of base-n, for example:

• 5 fingers make 1 hand
• 60 seconds make 1 minute, 60 minutes make 1 hour
• 365 days make 1 year
• 1024B = 1KB, 1024KB = 1MB, 1024MB = 1GB

✨ Decimal to Base-n Conversion

Decimal to base-n conversion involves converting the integer part and the fractional part separately. The process of converting decimal to base-n is very similar to finding what digit is in each place of a decimal number. If you cannot remember the specific method, you can work out the approach by thinking about how to extract each digit of a decimal number.

Integer Part Conversion

Method: Divide by base, collect remainders, reverse the order

Steps to convert a decimal integer to base-n:

1. Repeatedly integer-divide the decimal number by n, recording each remainder
2. Repeat until the quotient is 0
3. Arrange the remainders in reverse order to get the base-n integer

Example 1: Convert decimal 456 to binary

Find each digit's value from right to left:

Arranging remainders from bottom to top, the binary integer is: 111001000

Example 2: Convert decimal 100 to octal

Arranging remainders from bottom to top, the octal number is: 144

Verification: 1 * 8^2 + 4 * 8^1 + 4 * 8^0 = 64 + 32 + 4 = 100 ✓

Example 3: Convert decimal 255 to binary, octal, and hexadecimal

1. To binary (divide by 2, collect remainders):

   • 255 / 2 = 127 r1 -> 127 / 2 = 63 r1 -> 63 / 2 = 31 r1 -> 31 / 2 = 15 r1 -> 15 / 2 = 7 r1 -> 7 / 2 = 3 r1 -> 3 / 2 = 1 r1 -> 1 / 2 = 0 r1
   • Result: 11111111 (8 ones)

2. To octal (divide by 8, collect remainders):

   • 255 / 8 = 31 r7 -> 31 / 8 = 3 r7 -> 3 / 8 = 0 r3
   • Result: 377

3. To hexadecimal (divide by 16, collect remainders):

   • 255 / 16 = 15 r15(F) -> 15 / 16 = 0 r15(F)
   • Result: FF

Verification: 11111111(2) = 377(8) = FF(16) = 255(10) ✓

Fractional Part Conversion

Method: Multiply by base, collect integer parts, keep the order

Steps to convert a decimal fraction to base-n:

1. Multiply the fractional part of the decimal number by n, recording the integer part
2. Take the remaining fractional part and continue multiplying by n
3. Repeat until the fractional part becomes 0 (or the desired precision is reached)
4. Arrange the recorded integer parts in forward order to get the base-n fraction

Note: Integer conversion uses "reverse order" while fractional conversion uses "forward order" — the two directions are opposite, so do not mix them up!

Example 1: Convert decimal 0.625 to binary

Find each digit's value from left to right:

Binary fraction: 0.101

Verification: 1 * 2^(-1) + 0 * 2^(-2) + 1 * 2^(-3) = 0.5 + 0 + 0.125 = 0.625 ✓

Example 2: Convert decimal 0.7 to binary (infinite repeating fraction)

Binary fraction: 0.10110... (infinite repeating)

Tip: Not all decimal fractions can be exactly converted to base-n fractions — they may produce infinite repeating fractions. This is one of the root causes of floating-point precision issues in computers.

Sample Code

The following code converts a decimal integer to any base-n:

1#include <bits/stdc++.h>
2using namespace std;
3
4string decimal2base(int decimal_number, int base) {
5        if (decimal_number == 0) {
6                return "0";
7        }
8        string base_number;
9        while (decimal_number) {
10                int value = decimal_number % base;
11                char digit;
12                if (value < 10) {
13                        digit = value + '0';
14                } else {
15                        digit = value - 10 + 'A';
16                }
17                base_number += digit;
18                decimal_number /= base;
19        }
20        int len = base_number.length();
21        for (int i = 0; i < len / 2; ++i) {
22                swap(base_number[i], base_number[len - 1 - i]);
23        }
24        return base_number;
25}
26
27int main() {
28        int n;
29        cin >> n;
30        for (int i = 0; i < n; ++i) {
31                int base, decimal_number;
32                cin >> base >> decimal_number;
33                string base_number = decimal2base(decimal_number, base);
34                cout << base_number << endl;
35        }
36        return 0;
37}

✨ Base-n to Decimal Conversion

To convert from base-n to decimal, simply multiply each digit of the base-n number by its corresponding weight. The weight is the corresponding power of n, similar to finding the decimal value when each digit of a decimal number is known.

Integer Part Conversion

Method: Expand by weight, sum each digit

Steps to convert a base-n integer to decimal:

1. Starting from the rightmost digit, the weight is n^0 = 1
2. Multiply each digit's value by its corresponding weight (from right to left: n^0, n^1, n^2, ...)
3. Sum all results to get the decimal integer

Example 1: Convert binary 111001000 to decimal

Result: 256 + 128 + 64 + 8 = 456 ✓

Example 2: Convert hexadecimal 2A3 to decimal

Result: 512 + 160 + 3 = 675 ✓

Fractional Part Conversion

Method: Expand by weight, sum each digit (negative powers)

Steps to convert a base-n fraction to decimal:

1. Starting from the first digit after the decimal point, the weight is n^(-1)
2. Multiply each digit's value by its corresponding weight (from left to right: n^(-1), n^(-2), n^(-3), ...)
3. Sum all results to get the decimal fraction

Example: Convert binary fraction 0.101 to decimal

Result: 0.5 + 0 + 0.125 = 0.625 ✓

Horner's Method (Qin Jiushao Algorithm)

In code implementation, converting base-n to decimal typically does not require computing powers digit by digit. Instead, the more efficient Horner's method is used.

Core formula: decimal_number = decimal_number * base + value

Using hexadecimal "2A3" to decimal as an example, trace the execution:

This method accumulates from the most significant digit to the least significant digit, avoiding power calculations — very elegant and efficient.

Explanation: Taking "2A3" as an example, the expansion by weight is 2 * 16^2 + 10 * 16^1 + 3 * 16^0. By factoring out common factors, this transforms to ((2) * 16 + 10) * 16 + 3, which is exactly the computation order in the code.

Sample Code

The following code converts any base-n integer to decimal:

1#include <bits/stdc++.h>
2using namespace std;
3
4int base2decimal(string &base_number, int base) {
5        int decimal_number = 0;
6        int len = base_number.length();
7        for (int i = 0; i < len; ++i) {
8                char digit = base_number[i];
9                int value;
10                if (digit >= '0' && digit <= '9') {
11                        value = digit - '0';
12                }
13                if (digit >= 'A' && digit <='Z') {
14                        value = digit - 'A' + 10;
15                }
16                decimal_number = decimal_number * base + value;
17        }
18        return decimal_number;
19}
20
21int main() {
22        int n;
23        cin >> n;
24        for (int i = 0; i < n; ++i) {
25                int base;
26                string base_number;
27                cin >> base >> base_number;
28                int decimal_number = base2decimal(base_number, base);
29                cout << decimal_number << endl;
30        }
31        return 0;
32}

✨ Common Mistakes in Base Conversion

1. Reversing the remainder order: When converting decimal to base-n, remainders should be arranged from bottom to top (i.e., reversed). Many students arrange them in computation order, resulting in a reversed answer
2. Incorrect hexadecimal letter handling: In hexadecimal, 10-15 correspond to A-F. It is easy to forget to handle letters in code, or to write value - 10 + 'A' incorrectly
3. Wrong weight in base-n to decimal conversion: The rightmost digit's weight is n^0 = 1, not n^1. From right to left it goes n^0, n^1, n^2, ...
4. Not handling the special value 0: When the input is 0, the divide-and-collect-remainder loop does not execute, so you need a special case to directly output "0"
5. Mixing up integer and fractional conversion directions: Integer conversion is "divide by base, collect remainders, reverse order," while fractional conversion is "multiply by base, collect integer parts, keep order" — the two directions are opposite

III. Homework

Programming Exercises

1. Base Detection: L2114
2. Palindrome Squares: L2115

Knowledge Quiz

• Number Base Conversion - Quiz