Mã hóa số *

Tip

Trong cuốn sách này, các chương được đánh dấu hoa thị * là nội dung đọc thêm không bắt buộc. Nếu bạn không có nhiều thời gian hoặc cảm thấy chúng khó hiểu, bạn có thể tạm thời bỏ qua và quay lại đọc sau khi đã hoàn thành các chương cốt lõi.

Dấu lượng trị, bù 1 và bù 2

Trong bảng ở phần trước, chúng ta đã thấy rằng tất cả các kiểu số nguyên đều có thể biểu diễn số lượng số âm nhiều hơn số dương một số. Ví dụ, phạm vi của kiểu byte là \([-128, 127]\). Hiện tượng này có vẻ trái với lẽ thường, và nguyên nhân cốt lõi của nó nằm ở cách biểu diễn dấu lượng trị, bù 1 và bù 2.

Trước hết, cần lưu ý rằng các số được lưu trữ trong máy tính dưới dạng "bù 2". Trước khi phân tích nguyên nhân của điều này, chúng ta hãy cùng định nghĩa ba khái niệm sau.

• Dấu lượng trị (sign-magnitude): Chúng ta coi bit cao nhất (highest bit) trong biểu diễn nhị phân của một số là bit dấu, trong đó \(0\) biểu thị số dương và \(1\) biểu thị số âm, các bit còn lại biểu thị giá trị của số đó.
• Bù 1 (1's complement): Số bù 1 của một số dương tương tự như số dấu lượng trị của nó. Đối với số âm, số bù 1 được tạo ra bằng cách đảo ngược tất cả các bit ngoại trừ bit dấu trong số dấu lượng trị tương ứng của nó.
• Bù 2 (2's complement): Số bù 2 của một số dương tương tự như số dấu lượng trị của nó. Đối với số âm, số bù 2 được tạo ra bằng cách cộng thêm \(1\) vào số bù 1 của nó.

Hình dưới đây minh họa các phương pháp chuyển đổi qua lại giữa dấu lượng trị, bù 1 và bù 2.

Dấu lượng trị, mặc dù trực quan nhất, nhưng nó vẫn có một số hạn chế. Một mặt, không thể sử dụng trực tiếp số dấu lượng trị của số âm trong các phép tính toán. Ví dụ, việc tính toán \(1 + (-2)\) bằng dấu lượng trị sẽ cho ra kết quả là \(-3\), điều này rõ ràng là sai.

\[ \begin{aligned} & 1 + (-2) \newline & \rightarrow 0000 \; 0001 + 1000 \; 0010 \newline & = 1000 \; 0011 \newline & \rightarrow -3 \end{aligned} \]

Để giải quyết vấn đề này, máy tính đã đưa vào khái niệm bù 1. Nếu đầu tiên chúng ta chuyển đổi số dấu lượng trị sang số bù 1 và thực hiện phép tính \(1 + (-2)\) trong hệ bù 1, sau đó chuyển kết quả thu được trở lại dạng dấu lượng trị, chúng ta có thể nhận được kết quả chính xác là \(-1\).

\[ \begin{aligned} & 1 + (-2) \newline & \rightarrow 0000 \; 0001 \; \text{(Sign-magnitude)} + 1000 \; 0010 \; \text{(Sign-magnitude)} \newline & = 0000 \; 0001 \; \text{(1's complement)} + 1111 \; 1101 \; \text{(1's complement)} \newline & = 1111 \; 1110 \; \text{(1's complement)} \newline & = 1000 \; 0001 \; \text{(Sign-magnitude)} \newline & \rightarrow -1 \end{aligned} \]

Mặt khác, số dấu lượng trị của số không có hai cách biểu diễn là \(+0\) và \(-0\). Điều này có nghĩa là số không tương ứng với hai mã nhị phân khác nhau, dễ gây ra sự mơ hồ. Ví dụ, trong các phán đoán có điều kiện, nếu chúng ta không phân biệt giữa số không dương (\(+0\)) và số không âm (\(-0\)), nó có thể dẫn đến kết quả phán đoán không chính xác. Nếu muốn xử lý sự mơ hồ của số không dương (\(+0\)) và số không âm (\(-0\)), chúng ta cần đưa vào thêm các thao tác so sánh phán đoán phụ, điều này có thể làm giảm hiệu suất tính toán của máy tính.

\[ \begin{aligned} +0 & \rightarrow 0000 \; 0000 \newline -0 & \rightarrow 1000 \; 0000 \end{aligned} \]

Tương tự như dấu lượng trị, bù 1 cũng gặp phải vấn đề mơ hồ giữa số không dương (\(+0\)) và số không âm (\(-0\)). Vì vậy, máy tính đã giới thiệu thêm khái niệm bù 2. Trước hết, chúng ta hãy quan sát quá trình chuyển đổi số không âm (\(-0\)) từ dấu lượng trị sang bù 1 rồi sang bù 2:

\[ \begin{aligned} -0 \rightarrow \; & 1000 \; 0000 \; \text{(Sign-magnitude)} \newline = \; & 1111 \; 1111 \; \text{(1's complement)} \newline = 1 \; & 0000 \; 0000 \; \text{(2's complement)} \newline \end{aligned} \]

Cộng \(1\) vào số bù 1 của số không âm (\(-0\)) sẽ tạo ra một nhớ (carry), nhưng vì kiểu byte chỉ có độ dài 8 bit, số \(1\) bị tràn sang bit thứ 9 sẽ bị loại bỏ. Nghĩa là, số bù 2 của số không âm (\(-0\)) là \(0000 \; 0000\), giống hoàn toàn với số bù 2 của số không dương (\(+0\)). Điều này nghĩa là trong biểu diễn bù 2, chỉ tồn tại duy nhất một số không, và sự mơ hồ giữa số không dương (\(+0\)) và số không âm (\(-0\)) đã được giải quyết.

Một câu hỏi cuối cùng còn sót lại: Phạm vi của kiểu byte là \([-128, 127]\), vậy số âm dư ra \(-128\) từ đâu mà có? Chúng ta nhận thấy rằng tất cả các số nguyên trong khoảng \([-127, +127]\) đều có các biểu diễn dấu lượng trị, bù 1 và bù 2 tương ứng, đồng thời dạng dấu lượng trị và bù 2 có thể chuyển đổi qua lại cho nhau.

Tuy nhiên, số bù 2 \(1000 \; 0000\) là một ngoại lệ, và nó không có dạng dấu lượng trị tương ứng. Theo phương pháp chuyển đổi, chúng ta nhận thấy rằng dạng dấu lượng trị của số bù 2 này sẽ là \(0000 \; 0000\). Điều này rõ ràng là mâu thuẫn vì dạng dấu lượng trị đó biểu diễn số \(0\), mà số bù 2 của \(0\) phải là chính nó. Máy tính quy ước rằng số bù 2 đặc biệt \(1000 \; 0000\) này biểu diễn giá trị \(-128\). Trên thực tế, kết quả tính toán của phép cộng \((-1) + (-127)\) trong hệ bù 2 chính là \(-128\).

\[ \begin{aligned} & (-127) + (-1) \newline & \rightarrow 1111 \; 1111 \; \text{(Sign-magnitude)} + 1000 \; 0001 \; \text{(Sign-magnitude)} \newline & = 1000 \; 0000 \; \text{(1's complement)} + 1111 \; 1110 \; \text{(1's complement)} \newline & = 1000 \; 0001 \; \text{(2's complement)} + 1111 \; 1111 \; \text{(2's complement)} \newline & = 1000 \; 0000 \; \text{(2's complement)} \newline & \rightarrow -128 \end{aligned} \]

Bạn có thể đã nhận thấy rằng tất cả các phép tính toán ở trên đều là phép cộng. Điều này gợi mở một sự thật quan trọng: các mạch phần cứng bên trong máy tính chủ yếu được thiết kế dựa trên các phép toán cộng. Điều này là do phép cộng dễ triển khai trên phần cứng hơn so với các phép toán khác (như nhân, chia và trừ), dễ thực hiện song song hơn và có tốc độ tính toán nhanh hơn.

Xin lưu ý rằng điều này không có nghĩa là máy tính chỉ có thể thực hiện phép cộng. Bằng cách kết hợp phép cộng với một số phép toán logic cơ bản, máy tính có thể triển khai nhiều phép toán toán học khác. Ví dụ, phép trừ \(a - b\) có thể được chuyển đổi thành phép cộng \(a + (-b)\); phép nhân và phép chia có thể được chuyển đổi thành việc thực hiện nhiều lần phép cộng hoặc phép trừ.

Bây giờ chúng ta có thể tổng kết lý do tại sao máy tính sử dụng bù 2: nhờ cách biểu diễn bù 2, máy tính có thể sử dụng cùng một loại mạch và phép toán để xử lý phép cộng của cả số dương lẫn số âm, mà không cần thiết kế thêm mạch phần cứng đặc biệt cho phép trừ hoặc xử lý riêng sự mơ hồ giữa số không dương (\(+0\)) và số không âm (\(-0\)). Điều này giúp đơn giản hóa đáng kể thiết kế phần cứng và nâng cao hiệu suất.

Thiết kế của bù 2 cực kỳ khéo léo. Do giới hạn về mặt không gian của cuốn sách, chúng ta sẽ dừng lại tại đây. Độc giả quan tâm được khuyến khích tìm hiểu sâu hơn.

Mã hóa số thực dấu phẩy động

Độc giả tinh ý có thể đã nhận ra: int và float có cùng độ dài, đều là 4 byte, nhưng tại sao float lại có phạm vi biểu diễn lớn hơn nhiều so với int? Điều này rất kỳ lạ vì theo lẽ thường, float cần biểu diễn cả phần thập phân nên phạm vi biểu diễn của nó phải nhỏ đi.

Trên thực tế, đó là vì số thực float sử dụng một phương pháp biểu diễn khác. Hãy ký hiệu một số nhị phân 32-bit là:

\[ b_{31} b_{30} b_{29} \ldots b_2 b_1 b_0 \]

Theo tiêu chuẩn IEEE 754, một số float 32-bit bao gồm ba phần sau.

• Bit dấu \(\mathrm{S}\): chiếm 1 bit, tương ứng với \(b_{31}\).
• Bit mũ \(\mathrm{E}\): chiếm 8 bit, tương ứng với \(b_{30} b_{29} \ldots b_{23}\).
• Bit phần phân số \(\mathrm{N}\): chiếm 23 bit, tương ứng với \(b_{22} b_{21} \ldots b_0\).

Phương pháp tính toán giá trị tương ứng với số nhị phân float là:

\[ \text {val} = (-1)^{b_{31}} \times 2^{\left(b_{30} b_{29} \ldots b_{23}\right)_2-127} \times\left(1 . b_{22} b_{21} \ldots b_0\right)_2 \]

Khi chuyển đổi sang hệ thập phân, công thức tính toán là:

\[ \text {val}=(-1)^{\mathrm{S}} \times 2^{\mathrm{E} -127} \times (1 + \mathrm{N}) \]

Phạm vi của từng thành phần là:

\[ \begin{aligned} \mathrm{S} \in & \{ 0, 1\}, \quad \mathrm{E} \in \{ 1, 2, \dots, 254 \} \newline (1 + \mathrm{N}) = & (1 + \sum_{i=1}^{23} b_{23-i} 2^{-i}) \subset [1, 2 - 2^{-23}] \end{aligned} \]

Quan sát hình trên, với dữ liệu ví dụ \(\mathrm{S} = 0\), \(\mathrm{E} = 124\), \(\mathrm{N} = 2^{-2} + 2^{-3} = 0.375\), ta có:

\[ \text { val } = (-1)^0 \times 2^{124 - 127} \times (1 + 0.375) = 0.171875 \]

Giờ đây chúng ta đã có thể trả lời câu hỏi ban đầu: biểu diễn của float bao gồm bit mũ, dẫn đến phạm vi biểu diễn của nó lớn hơn nhiều so với int. Theo phép tính trên, số dương lớn nhất mà float có thể biểu diễn là \(2^{254 - 127} \times (2 - 2^{-23}) \approx 3.4 \times 10^{38}\), và số âm nhỏ nhất có thể thu được bằng cách đổi bit dấu.

Mặc dù số thực float mở rộng phạm vi biểu diễn, nhưng tác dụng phụ của nó là hy sinh độ chính xác. Kiểu số nguyên int sử dụng toàn bộ 32 bit để biểu diễn các số và các số này phân bố đều đặn; tuy nhiên, do sự tồn tại của bit mũ, giá trị của số thực float càng lớn thì khoảng cách chênh lệch giữa hai số kề nhau có xu hướng càng lớn.

Như được hiển thị trong bảng dưới đây, bit mũ \(\mathrm{E} = 0\) và \(\mathrm{E} = 255\) mang các ý nghĩa đặc biệt, được dùng để biểu diễn số không, vô cực, \(\mathrm{NaN}\), v.v.

Bảng   Ý nghĩa của các bit mũ

Bit mũ E	Bit phân số \(\mathrm{N} = 0\)	Bit phân số \(\mathrm{N} \ne 0\)	Công thức tính toán
\(0\)	\(\pm 0\)	Số phi chuẩn	\((-1)^{\mathrm{S}} \times 2^{-126} \times (0.\mathrm{N})\)
\(1, 2, \dots, 254\)	Số chuẩn	Số chuẩn	\((-1)^{\mathrm{S}} \times 2^{(\mathrm{E} -127)} \times (1.\mathrm{N})\)
\(255\)	\(\pm \infty\)	\(\mathrm{NaN}\)

Đáng chú ý là các số phi chuẩn cải thiện đáng kể độ chính xác của các số thực dấu phẩy động. Số chuẩn dương nhỏ nhất là \(2^{-126}\), và số phi chuẩn dương nhỏ nhất là \(2^{-126} \times 2^{-23}\).

Kiểu số thực chính xác kép double cũng sử dụng phương pháp biểu diễn tương tự như float, nên sẽ không được trình bày chi tiết ở đây.