CHUYÊN ĐỀ HỆ ĐẾM VÀ BIỂU DIỄN SỐ

Mục tiêu:

Hiểu rõ khái niệm hệ đếm cơ số b và cách biểu diễn một số ở dạng tổng quát.
Thành thạo các phương pháp chuyển đổi qua lại giữa các hệ đếm phổ biến: thập phân (10), nhị phân (2), bát phân (8), và thập lục phân (16).
Hiểu được mối quan hệ đặc biệt giữa các hệ đếm 2, 8, 16 và ứng dụng của nó trong việc chuyển đổi nhanh.
Nắm vững các phép toán số học cơ bản trên hệ nhị phân, là nền tảng cho các thao tác bit.
Nhận thức được tầm quan trọng của hệ nhị phân trong khoa học máy tính.

NỘI DUNG CHI TIẾT

Lời Mở Đầu: Tại Sao Không Phải Lúc Nào Cũng Là 10?

Câu chuyện: Từ thuở nhỏ, chúng ta đã quen với việc đếm mọi thứ bằng hệ thập phân (cơ số 10), một hệ thống hoàn toàn tự nhiên vì con người có 10 ngón tay. Nhưng máy tính thì sao? Thế giới của nó đơn giản hơn rất nhiều. Máy tính không có "ngón tay" theo nghĩa đen, nó chỉ hoạt động dựa trên hàng tỷ công tắc điện tử nhỏ bé. Mỗi công tắc chỉ có hai trạng thái: ON (có dòng điện chạy qua) hoặc OFF (không có dòng điện).
Giới thiệu: Đây chính là lý do tại sao hệ nhị phân (cơ số 2), với chỉ hai ký số 1 (ON) và 0 (OFF), trở thành ngôn ngữ gốc của mọi thiết bị kỹ thuật số. Tuy nhiên, làm việc với những chuỗi bit dài dằng dặc như 1101010010110101 là một cơn ác mộng đối với con người. Vì vậy, các hệ đếm khác như bát phân (cơ số 8) và thập lục phân (cơ số 16) ra đời như một cách "viết tắt" tiện lợi, giúp các lập trình viên đọc và biểu diễn dữ liệu nhị phân một cách ngắn gọn và hiệu quả hơn.
Mục đích chuyên đề: Chuyên đề này sẽ trang bị cho bạn những kiến thức nền tảng vững chắc, giúp bạn hiểu cách máy tính lưu trữ, biểu diễn và xử lý thông tin ở mức độ thấp nhất. Từ đó, bạn có thể hiểu sâu hơn về cấu trúc dữ liệu, các thuật toán tối ưu và cách hoạt động của thế giới số xung quanh mình.

Phần I: Khái Niệm Tổng Quát về Hệ Đếm Cơ Số `b`

Mục tiêu: Xây dựng nền tảng lý thuyết vững chắc.

Định nghĩa:
- Cơ số (Base / Radix): Là số lượng ký số (chữ số) riêng biệt được sử dụng trong một hệ đếm. Một hệ đếm cơ số (với là một số nguyên lớn hơn 1) sẽ sử dụng ký số, thường là từ 0 đến b-1.
- Giá trị vị trí (Place Value): Trong một hệ đếm theo vị trí, giá trị của một ký số không chỉ phụ thuộc vào bản thân nó mà còn phụ thuộc vào vị trí nó đứng. Mỗi vị trí trong một con số tương ứng với một lũy thừa của cơ số . Vị trí ngoài cùng bên phải có giá trị là , vị trí kế tiếp bên trái là , rồi đến , và cứ thế tiếp tục.
Dạng biểu diễn đa thức (Polynomial Representation):
- Bất kỳ một số nguyên nào được biểu diễn trong hệ cơ số dưới dạng đều có thể được viết dưới dạng một đa thức của . Giá trị của nó trong hệ thập phân là:
  Trong đó, là ký số ở vị trí thứ và .
- Ví dụ trực quan:
  - Số (123)₁₀ trong hệ thập phân có giá trị là: .
  - Số (1101)₂ trong hệ nhị phân có giá trị trong hệ thập phân là: . Vậy, (1101)₂ = (13)₁₀.

Phần II: Chuyển Đổi Giữa Các Hệ Đếm

Mục tiêu: Thành thạo các thuật toán chuyển đổi.

A. Chuyển đổi từ Hệ b sang Hệ Thập Phân (10)

Phương pháp: Cách tự nhiên nhất là áp dụng trực tiếp công thức đa thức đã nêu ở trên.
Thuật toán (Lược đồ Horner): Để tính toán hiệu quả hơn, tránh việc tính các lũy thừa lớn, ta có thể sử dụng lược đồ Horner. Công thức đa thức có thể được viết lại dưới dạng lồng nhau:

Thuật toán:
- Khởi tạo kết_quả = 0.
- Duyệt qua các ký số của số trong hệ b từ trái sang phải.
- Với mỗi ký số d, cập nhật kết_quả = kết_quả * b + giá_trị(d).

Code Mẫu (Python):

def from_base_b_to_decimal(num_str, base):
    """Chuyển một số từ hệ cơ số b (dưới dạng chuỗi) sang hệ thập phân."""
    decimal_value = 0
    hex_map = {'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}
    
    for digit in num_str:
        value = 0
        if '0' <= digit <= '9':
            value = int(digit)
        elif 'A' <= digit.upper() <= 'F':
            value = hex_map[digit.upper()]
        else:
            raise ValueError("Ký số không hợp lệ cho cơ số đã cho")

        if value >= base:
            raise ValueError(f"Ký số {digit} không hợp lệ cho cơ số {base}")

        decimal_value = decimal_value * base + value
        
    return decimal_value

# Ví dụ
print(f"(1101)₂ = {from_base_b_to_decimal('1101', 2)}₁₀")
print(f"(16E)₁₆ = {from_base_b_to_decimal('16E', 16)}₁₀")

B. Chuyển đổi từ Hệ Thập Phân (10) sang Hệ b

Phương pháp: Sử dụng phép chia lặp cho cơ số b và lấy phần dư. Phần dư của mỗi phép chia chính là các ký số của số trong hệ b, nhưng theo thứ tự từ phải sang trái.
Thuật toán:
- Cho số thập phân và cơ số .
- Lặp lại các bước sau trong khi :
  - Tính số dư: remainder = N % b. Đây là ký số tiếp theo (từ phải sang).
  - Cập nhật : N = N // b (chia lấy phần nguyên).
- Chuỗi các số dư thu được chính là biểu diễn của số trong hệ b nhưng bị ngược. Đảo ngược chuỗi này để có kết quả cuối cùng.

Code Mẫu (Python):

def from_decimal_to_base_b(decimal_num, base):
    """Chuyển một số từ hệ thập phân sang hệ cơ số b (kết quả là chuỗi)."""
    if decimal_num == 0:
        return "0"
        
    digits = "0123456789ABCDEF"
    result_str = ""
    
    n = decimal_num
    while n > 0:
        remainder = n % base
        result_str += digits[remainder]
        n //= base
        
    # Đảo ngược chuỗi để có kết quả đúng
    return result_str[::-1]

# Ví dụ
print(f"(13)₁₀ = ({from_decimal_to_base_b(13, 2)})₂")
print(f"(366)₁₀ = ({from_decimal_to_base_b(366, 16)})₁₆")

Phần III: Các Hệ Đếm Phổ Biến Trong Tin Học

Mục tiêu: Tập trung vào các hệ đếm quan trọng nhất.

A. Hệ Nhị Phân (Binary - Cơ số 2)

Ký số: {0, 1}. Mỗi ký số được gọi là một bit (viết tắt của BInary digiT), là đơn vị thông tin nhỏ nhất trong máy tính.
Tầm quan trọng: Là ngôn ngữ cơ bản của mọi thiết bị điện tử. Mọi dữ liệu, từ số, văn bản, hình ảnh, âm thanh, đều được mã hóa thành các chuỗi bit để máy tính có thể lưu trữ và xử lý.
Ví dụ:
- Chuyển (25)₁₀ sang nhị phân:
  - 25 / 2 = 12 dư 1
  - 12 / 2 = 6 dư 0
  - 6 / 2 = 3 dư 0
  - 3 / 2 = 1 dư 1
  - 1 / 2 = 0 dư 1
  - Đọc ngược lại: (11001)₂
- Chuyển (10110)₂ sang thập phân:

B. Hệ Bát Phân (Octal - Cơ số 8)

Ký số: {0, 1, 2, 3, 4, 5, 6, 7}.
Mối quan hệ với Nhị phân: 8 = 2³. Đây là mối quan hệ đặc biệt quan trọng. Mỗi một ký số bát phân tương ứng chính xác với một nhóm 3 bit nhị phân. Hệ bát phân từng được dùng để biểu diễn quyền truy cập file trong các hệ thống Unix/Linux (ví dụ chmod 755).
Bảng chuyển đổi: | Bát phân | Nhị phân | | :---: | :---: | | 0 | 000 | | 1 | 001 | | 2 | 010 | | 3 | 011 | | 4 | 100 | | 5 | 101 | | 6 | 110 | | 7 | 111 |

C. Hệ Thập Lục Phân (Hexadecimal - Cơ số 16)

Ký số: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}, trong đó A=10, B=11, ..., F=15.
Tầm quan trọng: Cực kỳ phổ biến trong tin học hiện đại vì nó biểu diễn dữ liệu nhị phân một cách rất ngắn gọn.
- Địa chỉ bộ nhớ: 0x7FFF...
- Mã màu HTML/CSS: #FF5733 (Mỗi cặp ký tự hex biểu diễn cường độ một màu: Đỏ, Xanh lá, Xanh dương).
- Địa chỉ MAC: 00:1A:2B:3C:4D:5E.
Mối quan hệ với Nhị phân: 16 = 2⁴. Mỗi một ký số thập lục phân tương ứng chính xác với một nhóm 4 bit nhị phân (còn gọi là một nibble). Vì một byte (8 bit) có thể được biểu diễn gọn gàng bằng hai ký tự hex, nó trở nên vô cùng tiện lợi.
Bảng chuyển đổi: | Hex | Nhị phân | Hex | Nhị phân | | :--: | :---: | :--: | :---: | | 0 | 0000 | 8 | 1000 | | 1 | 0001 | 9 | 1001 | | 2 | 0010 | A | 1010 | | 3 | 0011 | B | 1011 | | 4 | 0100 | C | 1100 | | 5 | 0101 | D | 1101 | | 6 | 0110 | E | 1110 | | 7 | 0111 | F | 1111 |

Phần IV: Kỹ Thuật Chuyển Đổi Nhanh (Shortcut Conversion)

Mục tiêu: Tận dụng mối quan hệ giữa các hệ 2, 8, 16.

A. Chuyển từ Nhị Phân sang Bát Phân / Thập Lục Phân

Thuật toán:
- Nhóm bit: Bắt đầu từ bit ngoài cùng bên phải, nhóm các bit của số nhị phân thành các cụm 3 bit (để chuyển sang hệ 8) hoặc 4 bit (để chuyển sang hệ 16).
- Thêm số 0 (Padding): Nếu nhóm bit cuối cùng bên trái không đủ số lượng, hãy thêm các chữ số 0 vào bên trái của nhóm đó cho đủ.
- Chuyển đổi từng nhóm: Tra bảng hoặc tính giá trị thập phân của mỗi nhóm bit, sau đó chuyển sang ký số tương ứng của hệ đích.
Ví dụ: Chuyển (101101110)₂
- Sang hệ 8 (nhóm 3 bit):
  - Nhóm: (101)(101)(110)₂
  - Chuyển đổi: (101)₂=5, (101)₂=5, (110)₂=6
  - Kết quả: (556)₈
- Sang hệ 16 (nhóm 4 bit):
  - Nhóm từ phải qua: (1110) và (0110) và (1)
  - Thêm số 0 vào nhóm cuối: (0001)(0110)(1110)₂
  - Chuyển đổi: (0001)₂=1, (0110)₂=6, (1110)₂=E
  - Kết quả: (16E)₁₆

B. Chuyển từ Bát Phân / Thập Lục Phân sang Nhị Phân

Thuật toán:
- Lấy từng ký số của hệ nguồn.
- Chuyển mỗi ký số đó sang nhóm 3 bit (nếu từ hệ 8) hoặc 4 bit (nếu từ hệ 16) tương ứng.
- Nối các nhóm bit lại với nhau. Có thể loại bỏ các số 0 vô nghĩa ở đầu kết quả.
Ví dụ:
- Chuyển (3A5)₁₆ sang nhị phân:
  - Chuyển đổi: 3 -> (0011), A -> (1010), 5 -> (0101)
  - Nối lại: 0011 1010 0101
  - Kết quả: (1110100101)₂
- Chuyển (556)₈ sang nhị phân:
  - Chuyển đổi: 5 -> (101), 5 -> (101), 6 -> (110)
  - Nối lại: 101 101 110
  - Kết quả: (101101110)₂

Phần V: Số Học Nhị Phân và Thao Tác Bit

Mục tiêu: Liên kết hệ đếm với các phép toán máy tính.

Phép cộng nhị phân:
- Các quy tắc cơ bản:
  - 0 + 0 = 0
  - 0 + 1 = 1
  - 1 + 0 = 1
  - 1 + 1 = 0, nhớ 1 (carry 1)
- Ví dụ: Cộng (1101)₂ và (1011)₂ (tức là 13 + 11 = 24).
```
  1 1 1   (số nhớ - carry)
  1 1 0 1  (13)
+ 1 0 1 1  (11)
---------
1 1 0 0 0  (24)
```
Giới thiệu các phép toán bit (Bitwise Operations): Đây là các phép toán cấp thấp, thực hiện trực tiếp trên các bit của một số. Chúng cực kỳ nhanh và là nền tảng cho nhiều kỹ thuật tối ưu.
- AND (&): Kết quả là 1 chỉ khi cả hai bit toán hạng đều là 1.
  - 0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1
- OR (|): Kết quả là 1 nếu ít nhất một trong hai bit toán hạng là 1.
  - 0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1
- XOR (^): Kết quả là 1 nếu hai bit toán hạng khác nhau.
  - 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0
- NOT (~): Đảo ngược tất cả các bit của một số (0 thành 1 và 1 thành 0).
- Dịch trái (<< n): Dịch chuyển các bit sang trái n vị trí. Các vị trí trống bên phải được điền bằng 0. Thao tác này tương đương với phép nhân số đó với .
  - Ví dụ: (1101)₂ << 2 (13 << 2) -> (110100)₂ (52). .
- Dịch phải (>> n): Dịch chuyển các bit sang phải n vị trí. Các vị trí trống bên trái được điền bằng 0 (với số không dấu). Thao tác này tương đương với phép chia nguyên cho .
  - Ví dụ: (11010)₂ >> 1 (26 >> 1) -> (1101)₂ (13). .
- Liên kết: Các phép toán này là công cụ mạnh mẽ trong lập trình. Ví dụ, AND dùng để kiểm tra một bit cụ thể có được bật hay không, OR dùng để bật một bit, XOR dùng để đảo trạng thái một bit. Kỹ thuật dùng các bit của một số nguyên để biểu diễn một tập hợp các trạng thái được gọi là Bitmask, là nền tảng cho lớp bài toán Quy hoạch động trạng thái (Bitmask DP).

Phần VI: Bài Tập Luyện Tập

Level 1 (Cơ bản):
1. Chuyển các số sau sang hệ thập phân: (101101)₂, (72)₈, (A3F)₁₆.
2. Chuyển số (150)₁₀ sang các hệ nhị phân, bát phân và thập lục phân.
3. Sử dụng phương pháp chuyển đổi nhanh:
  - Chuyển (11010110111101)₂ sang hệ 8 và hệ 16.
  - Chuyển (FACE)₁₆ sang hệ nhị phân.
  - Chuyển (771)₈ sang hệ nhị phân.
Level 2 (Lập trình):
1. Bài toán: Viết một hàm nhận vào một số nguyên n và một cơ số b (2 <= b <= 36), trả về chuỗi biểu diễn số n trong hệ cơ số b.
2. Bài toán: Viết một hàm nhận vào một chuỗi s biểu diễn một số trong hệ cơ số b và cơ số b, trả về giá trị thập phân của nó. (Về cơ bản là hiện thực lại các hàm trong Phần II).
3. Thử thách: Tìm hiểu và giải bài "Convert to Base -2" trên LeetCode để xử lý trường hợp cơ số âm.
Level 3 (Ứng dụng):
1. Đếm số bit 1: Cho một số nguyên n, đếm xem có bao nhiêu bit 1 trong biểu diễn nhị phân của nó. (Ví dụ: n=13 -> (1101)₂ -> có 3 bit 1). Tìm kiếm "Brian Kernighan's algorithm" để có một giải pháp tối ưu. (Bài toán "Number of 1 Bits" và "Counting Bits" trên LeetCode).
2. Số đối xứng trong hệ nhị phân (Palindromic Number): Kiểm tra xem biểu diễn nhị phân của một số nguyên dương có phải là một chuỗi đối xứng hay không (bỏ qua các số 0 ở đầu). (Ví dụ: n=9 -> (1001)₂ là đối xứng).
3. Cộng hai số nhị phân: Cho hai chuỗi biểu diễn hai số nhị phân, trả về tổng của chúng (cũng dưới dạng chuỗi nhị phân). (Bài toán "Add Binary" trên LeetCode).
4. Quy hoạch động Bitmask: Đây là một chủ đề nâng cao. Tìm hiểu về kỹ thuật này và thử sức với các bài toán kinh điển như "Traveling Salesperson Problem" với N nhỏ, hoặc các bài tập trên VNOI Wiki (mục Chuyên đề / Quy hoạch động bitmask).