Hệ đếm và biểu diễn số
Trước khi viết một dòng lệnh C, ta cần hiểu máy tính thực ra lưu trữ thông tin như thế nào. Con người trao đổi bằng chữ viết, hình ảnh, âm thanh; còn bên trong máy tính chỉ có các mạch điện, mỗi mạch chỉ có hai trạng thái: có điện hoặc không có điện, bật hoặc tắt. Người ta quy ước hai trạng thái này là 1 và 0. Tất cả những gì máy tính làm, từ hiển thị một bức ảnh đến chơi một bản nhạc, suy cho cùng đều được biểu diễn bằng những dãy số 0 và 1. Bài học này xây dựng nền tảng đó: bit và byte, các hệ đếm và cách chuyển đổi, cuối cùng là các phép toán làm việc trực tiếp trên bit.
Thử ngay: xem hệ đếm chuyển đổi từng bước
Chưa cần biết gì về các hệ đếm, bạn cứ tự tay thử công cụ dưới đây trước đã. Chọn một số thập phân bất kỳ từ 0 đến 255 rồi xem ngay dạng nhị phân, bát phân và thập lục phân của nó, đổi cơ số đích để theo dõi bảng chia lấy dư tương ứng. Hãy để ý các số dư luôn được đọc từ dưới lên mới ghép ra kết quả. Bốn hệ đếm ấy khác nhau ra sao, vì sao lại chia lấy dư và vì sao phải đọc ngược, các mục bên dưới sẽ giải thích lần lượt.
65(hệ 8)35(hệ 16)| Phép chia | Thương | Số dư |
|---|---|---|
| 53 / 2 = | 26 | 1 |
| 26 / 2 = | 13 | 0 |
| 13 / 2 = | 6 | 1 |
| 6 / 2 = | 3 | 0 |
| 3 / 2 = | 1 | 1 |
| 1 / 2 = | 0 | 1 |
110101 (nhị phân (cơ số 2)).Bit và byte
Đơn vị thông tin nhỏ nhất trong máy tính là bit (viết tắt của binary digit). Một bit chỉ nhận một trong hai giá trị: 0 hoặc 1. Một bit thì quá ít, chỉ phân biệt được hai khả năng. Để biểu diễn nhiều thông tin hơn, ta gom nhiều bit lại. Tám bit ghép lại thành một byte.
Một byte biểu diễn được 2^8 = 256 tổ hợp khác nhau, tức 256 giá trị, thường đánh số từ 0 đến 255. Vì sao lại là 256? Hãy hình dung 8 ô, mỗi ô điền 0 hoặc 1. Ô thứ nhất có 2 lựa chọn, ô thứ hai có 2 lựa chọn, cứ thế. Tổng số cách điền là 2 * 2 * ... * 2 (tám lần), tức 2^8 = 256. Cách suy luận này rất quan trọng: cứ thêm một bit thì số tổ hợp tăng gấp đôi.
Một byte có thể dùng để lưu một số nguyên từ 0 đến 255, hoặc một ký tự theo bảng mã ASCII. Ví dụ chữ cái A được máy tính lưu dưới dạng byte 01000001, tương ứng số 65. Khi ta gõ phím A, máy không lưu hình dạng chữ A, mà lưu con số 65.
Vì byte vẫn nhỏ so với nhu cầu thực tế, người ta dùng các bội số lớn hơn:
| Đơn vị | Quy đổi | Hình dung |
|---|---|---|
| 1 byte | 8 bit | một ký tự |
| 1 KB (kilobyte) | 1024 byte | một đoạn văn ngắn |
| 1 MB (megabyte) | 1024 KB | một bức ảnh |
| 1 GB (gigabyte) | 1024 MB | một bộ phim |
| 1 TB (terabyte) | 1024 GB | cả một ổ cứng |
Trong máy tính, các bội số tăng theo lũy thừa của 2 chứ không phải của 10. Vì vậy 1 KB là 1024 byte (tức 2^10) chứ không phải tròn 1000 byte như cách nói thông thường.
Các hệ đếm
Hằng ngày ta đếm bằng hệ thập phân (decimal), dùng mười chữ số từ 0 đến 9. Sở dĩ gọi là hệ cơ số 10 vì mỗi khi đếm hết các chữ số thì ta lùi sang cột bên trái và bắt đầu lại. Máy tính, như đã nói, làm việc với 0 và 1 nên dùng hệ nhị phân (binary), tức hệ cơ số 2. Ngoài ra trong lập trình ta còn gặp hệ bát phân (octal) cơ số 8 và hệ thập lục phân (hexadecimal) cơ số 16.
Vì sao máy tính chọn nhị phân
Ta có thể hỏi ngược: sao không chế tạo máy tính chạy thẳng bằng hệ thập phân cho gần với con người? Câu trả lời nằm ở phần cứng. Mỗi đường mạch phải phân biệt được các mức tín hiệu, mà phân biệt hai mức thì chắc chắn hơn hẳn phân biệt mười mức: với nhị phân chỉ cần hỏi có điện hay không, mức điện trồi sụt đôi chút vì nhiễu thì hai trạng thái vẫn không lẫn vào nhau, còn mười mức điện áp thì chỉ một dao động nhỏ đã đủ làm máy đọc nhầm 6 thành 7. Gốc rễ vì thế là độ tin cậy: hai trạng thái rạch ròi cho phép mạch chạy nhanh, rẻ và ít lỗi, nên mọi lớp bên trên cuối cùng đều quy về các dãy 0 và 1.
Giá trị theo vị trí
Điểm cốt lõi của mọi hệ đếm là giá trị một chữ số phụ thuộc vào vị trí của nó. Trong hệ thập phân, số 345 nghĩa là:
345 = 3 * 10^2 + 4 * 10^1 + 5 * 10^0 = 300 + 40 + 5
Cột ngoài cùng bên phải ứng với 10^0, kế đó là 10^1, rồi 10^2, cứ thế nhân dần lên. Hệ nhị phân hoạt động y hệt, chỉ thay cơ số 10 bằng cơ số 2:
1011 (hệ 2) = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 8 + 0 + 2 + 1 = 11 (hệ 10)
Ta thường ghi chú số đó đang ở hệ nào để khỏi nhầm, ví dụ 1011 (hệ 2) khác hẳn 1011 (hệ 10).
Trong một số ở hệ cơ số b, chữ số ở vị trí thứ k tính từ phải (bắt đầu đếm từ 0) có trọng số b^k. Giá trị của cả số bằng tổng của từng chữ số nhân với trọng số tương ứng.
Hệ thập lục phân
Hệ thập lục phân cần 16 chữ số, nhưng ta chỉ có sẵn 10 chữ số 0 đến 9. Để có thêm 6 chữ số nữa, người ta mượn các chữ cái: A cho 10, B cho 11, C cho 12, D cho 13, E cho 14, F cho 15. Hệ này rất tiện vì mỗi chữ số thập lục phân gói gọn đúng 4 bit nhị phân.
Bảng dưới đối chiếu các số từ 0 đến 15 ở ba hệ. Hãy ghi nhớ bảng này, nó sẽ được dùng đi dùng lại:
| Thập phân | Nhị phân | Hex | Thập phân | Nhị phân | Hex |
|---|---|---|---|---|---|
| 0 | 0000 | 0 | 8 | 1000 | 8 |
| 1 | 0001 | 1 | 9 | 1001 | 9 |
| 2 | 0010 | 2 | 10 | 1010 | A |
| 3 | 0011 | 3 | 11 | 1011 | B |
| 4 | 0100 | 4 | 12 | 1100 | C |
| 5 | 0101 | 5 | 13 | 1101 | D |
| 6 | 0110 | 6 | 14 | 1110 | E |
| 7 | 0111 | 7 | 15 | 1111 | F |
Chuyển đổi giữa các hệ đếm
Việc chuyển qua lại giữa các hệ là kỹ năng cơ bản. Tóm tắt phương pháp cho từng chiều:
| Chiều chuyển | Phương pháp |
|---|---|
| thập phân sang nhị phân | chia 2 lấy số dư, đọc dư từ dưới lên |
| nhị phân sang thập phân | nhân từng bit với trọng số rồi cộng |
| thập phân sang thập lục phân | chia 16 lấy số dư |
| nhị phân và thập lục phân | gom hoặc tách nhóm 4 bit |
Từ nhị phân sang thập phân
Đây là chiều dễ nhất. Ta nhân từng chữ số với trọng số rồi cộng lại, đúng như công thức giá trị theo vị trí. Đổi 110101 (hệ 2) sang thập phân, viết trọng số dưới mỗi chữ số rồi cộng các vị trí có chữ số 1:
110101 (hệ 2) = 1*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0
= 32 + 16 + 4 + 1 = 53 (hệ 10)
Từ thập phân sang nhị phân
Ta dùng phương pháp chia lấy số dư: chia số thập phân cho 2, ghi lại số dư (0 hoặc 1), rồi lấy thương chia tiếp cho 2, cứ thế cho tới khi thương bằng 0. Đọc các số dư theo chiều ngược lại, từ dưới lên, sẽ được kết quả nhị phân. Đổi 53 (hệ 10) sang nhị phân:
53 / 2 = 26 dư 1
26 / 2 = 13 dư 0
13 / 2 = 6 dư 1
6 / 2 = 3 dư 0
3 / 2 = 1 dư 1
1 / 2 = 0 dư 1
Đọc các số dư từ dưới lên: 110101 (hệ 2). Đúng bằng số ở ví dụ trước, một cách kiểm chứng tốt.
Giữa nhị phân và thập lục phân
Đây là lý do hệ thập lục phân được ưa dùng. Vì mỗi chữ số hex ứng với đúng 4 bit (xem lại bảng đối chiếu), ta đổi qua lại chỉ bằng cách gom hoặc tách nhóm 4 bit, không cần làm phép chia nào. Đổi 11010110 (hệ 2) sang thập lục phân, tách dãy bit thành các nhóm 4 bit, tính từ phải sang trái:
1101 0110
D 6
Nhóm 1101 là 13, viết là D; nhóm 0110 là 6. Vậy 11010110 (hệ 2) bằng D6 (hệ 16). Ngược lại, muốn đổi D6 (hệ 16) sang nhị phân, ta thay mỗi chữ số bằng 4 bit của nó: D thành 1101, 6 thành 0110, ghép lại được 11010110.
Khi tách nhóm 4 bit, luôn bắt đầu đếm từ bên phải. Nếu nhóm bên trái thiếu bit thì thêm số 0 vào đầu cho đủ 4. Ví dụ 1101101 (7 bit) được tách thành 0110 và 1101, tức 6D (hệ 16).
Hệ bát phân
Hệ bát phân cơ số 8 dùng tám chữ số 0 đến 7 và mỗi chữ số ứng với đúng 3 bit. Cách đổi hoàn toàn tương tự hệ thập lục phân, chỉ khác là gom nhóm 3 bit thay vì 4. Ví dụ 110101 (hệ 2) tách thành 110 và 101, tức 65 (hệ 8). Hệ bát phân ngày nay ít dùng hơn hệ thập lục phân nên ta chỉ giới thiệu ở mức nhận biết.
Biểu diễn số âm và tràn số
Tới giờ ta mới bàn các số không âm. Máy tính biểu diễn số âm bằng một quy ước gọi là bù
hai (two's complement): trong một ô n bit, số âm -x được lưu bằng dạng bit của
2^n - x. Cách làm nhanh để lấy -x là đảo tất cả các bit của x rồi cộng thêm 1. Ví
dụ với 8 bit, số 5 là 00000101; đảo bit thành 11111010, cộng 1 ra 11111011, đó
chính là -5. Bit ngoài cùng bên trái đóng vai bit dấu: bằng 1 thì số âm, bằng 0 thì số
không âm. Nhờ bù hai, phần cứng cộng trừ số âm và số dương chỉ bằng đúng một mạch cộng,
không cần xử lý dấu riêng, đó là lý do quy ước này được chọn.
Vì mỗi kiểu số chỉ có số bit cố định, luôn có một giá trị lớn nhất mà nó chứa được. Khi
phép tính vượt qua ngưỡng đó, kết quả không còn đủ chỗ và ta gặp tràn số (overflow). Một
byte không dấu chứa từ 0 tới 255; cộng 1 vào 255 sẽ quay vòng về 0, giống kim đồng hồ
quay hết vòng lại về đầu. Kiểu unsigned trong C được bảo đảm quay vòng đúng như vậy.
Nhiều người tưởng số có dấu cũng lặng lẽ quay vòng như unsigned, nhưng chuẩn C không
hứa điều đó. Tràn một số nguyên có dấu, chẳng hạn cộng 1 vào giá trị int lớn nhất, là
hành vi không xác định: trình biên dịch được phép giả định điều đó không bao giờ xảy ra
rồi tối ưu dựa trên giả định ấy, nên chương trình có thể cho kết quả vô lý, bỏ qua cả một
nhánh kiểm tra, hay đổ vỡ tuỳ mức tối ưu. Gốc rễ là chuẩn cố tình bỏ ngỏ để phần cứng
mỗi loại tự do cài đặt cách nhanh nhất. Chỉ unsigned mới được bảo đảm quay vòng theo
2^n, nên đừng dựa vào tràn số có dấu, hãy kiểm tra ngưỡng trước khi cộng.
Phép toán trên bit
Vì dữ liệu trong máy là các dãy bit, máy tính cung cấp một nhóm phép toán làm việc trực tiếp trên từng bit. Các phép cơ bản gồm:
- AND (và): kết quả bằng 1 chỉ khi cả hai bit đều bằng 1. Trong C viết bằng dấu
&. - OR (hoặc): kết quả bằng 1 khi có ít nhất một bit bằng 1. Trong C viết bằng dấu
|. - XOR (hoặc loại trừ): kết quả bằng 1 khi hai bit khác nhau. Trong C viết bằng dấu
^. - NOT (đảo): biến 0 thành 1 và 1 thành 0. Trong C viết bằng dấu
~. - Dịch bit (shift): đẩy toàn bộ dãy bit sang trái hoặc phải một số vị trí, trong C viết bằng
<<và>>.
Cho hai số 4 bit A = 1100 và B = 1010, thực hiện từng cặp bit theo cột:
| bit 3 | bit 2 | bit 1 | bit 0 | |
|---|---|---|---|---|
| A | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 |
| A AND B | 1 | 0 | 0 | 0 |
| A OR B | 1 | 1 | 1 | 0 |
| A XOR B | 0 | 1 | 1 | 0 |
Dịch trái dãy 1100 một vị trí ta được 11000, tương đương nhân số đó với 2.
Dịch trái một bit tương đương nhân 2, dịch phải một bit tương đương chia 2 (bỏ phần dư). Đây là lý do các phép dịch bit chạy rất nhanh và hay được dùng để tối ưu. Trong C, phép x << 1 cho ra x * 2, còn x >> 1 cho ra x / 2.
Một thoáng nhìn trước trong C
Các phép toán bit trên đây sẽ được học kỹ ở chương sau, nhưng để hình dung, đây là cách chúng xuất hiện trong một chương trình C thật:
#include <stdio.h>
int main(void) {
unsigned char a = 12; // 1100 in binary
unsigned char b = 10; // 1010 in binary
printf("a AND b = %d\n", a & b); // 8
printf("a OR b = %d\n", a | b); // 14
printf("a XOR b = %d\n", a ^ b); // 6
printf("a << 1 = %d\n", a << 1); // 24, same as a * 2
printf("a >> 1 = %d\n", a >> 1); // 6, same as a / 2
return 0;
}
Đừng lo nếu cú pháp còn lạ. Điều cần nhớ bây giờ là máy tính lưu mọi thứ bằng bit, và các phép toán bit thao tác trực tiếp lên những bit đó.
Viết hằng số theo cơ số trong C
Trong mã C, một số viết bình thường được hiểu là hệ thập phân, nhưng ta có thể viết thẳng theo cơ số khác nhờ tiền tố. Số bắt đầu bằng 0x hoặc 0X là thập lục phân, ví dụ 0xFF chính là 255. Số bắt đầu bằng một chữ số 0 đứng trước các chữ số khác là bát phân: gõ 012 tưởng là mười hai nhưng máy đọc ra 10, chỉ vì con số 0 vô tình đặt ở đầu. Dù viết theo cơ số nào, giá trị lưu trong bộ nhớ vẫn là cùng một dãy bit; cơ số chỉ là cách ta ghi ra cho dễ đọc, còn 255, 0xFF và 0377 cùng trỏ tới đúng một giá trị.
Bài tập thực hành
Bài 1. Một byte gồm bao nhiêu bit và biểu diễn được bao nhiêu giá trị khác nhau? Giải thích vì sao thêm một bit thì số tổ hợp tăng gấp đôi.
Gợi ý
Một byte gồm 8 bit, biểu diễn được 2^8 = 256 giá trị (từ 0 đến 255). Thêm một bit nghĩa là thêm một ô có 2 lựa chọn, nên tổng số tổ hợp được nhân thêm 2, tức tăng gấp đôi.
Bài 2. Đổi các số nhị phân sau sang hệ thập phân: a) 1001; b) 11110; c) 101010.
Gợi ý
Nhân từng bit với trọng số rồi cộng. a) 1001 = 8 + 1 = 9. b) 11110 = 16 + 8 + 4 + 2 = 30. c) 101010 = 32 + 8 + 2 = 42.
Bài 3. Đổi các số thập phân sau sang hệ nhị phân bằng phương pháp chia lấy số dư: a) 19; b) 42; c) 100.
Gợi ý
Chia liên tiếp cho 2 và đọc số dư từ dưới lên. a) 19 ra 10011. b) 42 ra 101010. c) 100 ra 1100100. Có thể kiểm chứng ngược bằng cách đổi lại sang thập phân.
Bài 4. Đổi sang hệ thập lục phân bằng cách gom nhóm 4 bit: a) 10110100; b) 11111111. Sau đó đổi ngược 2F (hệ 16) và A0 (hệ 16) về nhị phân.
Gợi ý
a) 1011 0100 ra B4. b) 1111 1111 ra FF. Ngược lại: 2F thành 0010 1111, tức 00101111; A0 thành 1010 0000, tức 10100000.
Bài 5. Cho hai số 4 bit A = 1011 và B = 0110. Tính A AND B, A OR B, A XOR B theo từng cột bit.
Gợi ý
Xét từng cột. A AND B = 0010. A OR B = 1111. A XOR B = 1101. Nhớ quy tắc: AND lấy 1 khi cả hai bằng 1, OR lấy 1 khi ít nhất một bằng 1, XOR lấy 1 khi hai bit khác nhau.
Câu hỏi tự kiểm
- 1Một byte gồm 8 bit thì biểu diễn được bao nhiêu giá trị khác nhau?
- 2Nhóm 4 bit 1101 đổi sang một chữ số thập lục phân là gì?
- 3Trong mã C, hằng số viết là 012 có giá trị thập phân là bao nhiêu?
- 4Khi phép tính vượt phạm vi, kiểu số nào được chuẩn C bảo đảm quay vòng theo 2 mũ n?
Máy tính lưu mọi thông tin bằng bit, gom 8 bit thành 1 byte biểu diễn 256 giá trị. Mọi hệ đếm hoạt động theo nguyên tắc giá trị theo vị trí: chữ số ở vị trí k có trọng số là cơ số mũ k. Đổi thập phân sang nhị phân bằng chia 2 lấy số dư, đổi giữa nhị phân và thập lục phân chỉ cần gom hoặc tách nhóm 4 bit. Các phép toán bit AND, OR, XOR, NOT và dịch bit thao tác trực tiếp trên từng bit, trong đó dịch trái một bit tương đương nhân 2.