Hệ đếm: bài tập có lời giải từng bước

1Hệ đếm là gì

Trong đời sống hằng ngày bạn đếm theo hệ thập phân, cơ số 10. Nó có mười chữ số, từ 0 đến 9, và mỗi hàng có giá trị gấp mười lần hàng bên phải nó.

Trong 352, số 3 có giá trị 300, số 5 có giá trị 50 và số 2 có giá trị 2. Các hàng có giá trị 1, 10, 100 tính từ bên phải.

Máy tính lưu mọi thứ dưới dạng các công tắc bật hoặc tắt. Vì vậy nó đếm theo hệ nhị phân, cơ số 2, chỉ với hai chữ số 0 và 1.

Một chữ số nhị phân là một bit. Một nhóm 8 bit là một byte.

Quy tắc giống nhau ở mọi cơ số: mỗi chữ số có giá trị bằng giá trị của nó nhân với một lũy thừa của cơ số.

2Nhị phân và thập lục phân

Trong hệ nhị phân, các hàng có giá trị 1, 2, 4, 8, 16 và cứ thế, tính từ bên phải. Mỗi hàng có giá trị gấp đôi hàng bên phải nó.

Với số 8 bit, các hàng có giá trị 128, 64, 32, 16, 8, 4, 2 và 1.

Để đọc một số nhị phân, hãy cộng giá trị hàng của mọi bit bằng 1. Với 0011 0010 đó là 32 + 16 + 2 = 50.

Các dãy bit dài rất khó đọc. Lập trình viên thường viết chúng bằng hệ thập lục phân (hex), cơ số 16, thay vào đó.

Hex cần 16 chữ số. Nó dùng 0 đến 9 rồi các chữ cái A = 10, B = 11, C = 12, D = 13, E = 14 và F = 15.

Các hàng hex có giá trị 1, 16, 256 và 4096, tính từ bên phải. Một số hex thường được viết với 0x ở đầu, ví dụ 0x2F.

Một chữ số hex đúng bằng 4 bit, nên 0011 0010 là 0x32: 0011 là 3 và 0010 là 2.

3Số âm: bù hai

Một byte có mọi hàng đều dương lưu các số từ 0 đến 255. Cách này gọi là không dấu.

Để lưu số âm, máy tính dùng bù hai. Thay đổi duy nhất là bit ngoài cùng bên trái có giá trị −128 thay vì +128.

Vậy 1000 0011 là −128 + 2 + 1 = −125. Bit ngoài cùng bên trái gọi là bit dấu: khi nó bằng 1, số đó âm.

Một số bù hai 8 bit chạy từ −128 (1000 0000) đến +127 (0111 1111).

Để viết số âm −x, bắt đầu từ +x ở dạng nhị phân, đảo mọi bit (0 thành 1, 1 thành 0) rồi cộng 1.

Ví dụ với −5: 5 là 0000 0101. Đảo bit được 1111 1010. Cộng 1 được 1111 1011.

Cùng dãy bit đó đọc theo không dấu có giá trị 256 − x. Với −5 đó là 251, và 1111 1011 đúng là 128 + 64 + 32 + 16 + 8 + 2 + 1 = 251.

4Phương pháp từng bước

Nhị phân hoặc hex sang thập phân:

1. Viết giá trị hàng dưới mỗi chữ số: các lũy thừa của 2 cho nhị phân, các lũy thừa của 16 cho hex, bắt đầu bằng 1 ở bên phải.
2. Trong hex, thay mỗi chữ cái bằng giá trị của nó: A = 10 cho đến F = 15.
3. Nhân mỗi chữ số với giá trị hàng của nó rồi cộng tất cả lại.

Bù hai:

1. Để đọc một dãy bit, cho bit ngoài cùng bên trái giá trị −128 (với 8 bit) và cộng giá trị hàng của tất cả các bit 1.
2. Để viết −x, viết +x bằng 8 bit, đảo mọi bit rồi cộng 1.
3. Giá trị không dấu của dãy bit đó là 256 − x. Dùng nó để kiểm tra các bit của bạn.

Bit, phạm vi và bộ nhớ:

1. n bit cho 2ⁿ dãy khác nhau.
2. Không dấu thì chúng lưu 0 đến 2ⁿ − 1. Với bù hai thì chúng lưu −2ⁿ⁻¹ đến 2ⁿ⁻¹ − 1.
3. Để mỗi trong k mục có mã riêng, tìm b nhỏ nhất sao cho 2^b ≥ k.
4. Với bộ nhớ, nhân số mục với số bit mỗi mục, rồi chia cho 8 để ra byte và chia cho 1024 để ra KiB.

5Một ví dụ có lời giải

Theo dõi từng bước. Hãy thử đoán bước tiếp theo trước khi mở nó.

6Lỗi thường gặp

• Quên cộng 1 sau khi đảo bit. Kết quả sẽ thấp hơn một.
• Đọc một dãy bù hai như số không dấu, ví dụ 1111 1111 là 255 thay vì −1.
• Coi bit dấu như dấu trừ đứng trước các bit khác. Trong bù hai nó có giá trị −128.
• Đặt các hàng sai thứ tự. Hàng có giá trị 1 luôn ở bên phải.
• Dùng A = 11 trong hex. Các chữ cái bắt đầu từ A = 10.
• Lẫn bit với byte trong các câu hỏi về bộ nhớ. Hãy chia số bit cho 8.

7Các câu hỏi thi trông như thế nào

• Dễ: nhị phân và hex sang thập phân. Chuyển một số nhị phân 8 bit hoặc một số hex 3 chữ số sang thập phân.
• Trung bình: số bù hai. Đọc giá trị của một chuỗi 8 bit có dấu, hoặc viết một số âm thành chuỗi bit và cho biết giá trị không dấu của nó.
• Khó: bit, miền giá trị và bộ nhớ. Giá trị lớn nhất hoặc âm nhất biểu diễn được bằng n bit, số bit cần có cho k mã, hoặc dung lượng bộ nhớ của một ảnh.

Ví dụ một câu hỏi khó: một ảnh 256 × 256 với 24 bit mỗi điểm ảnh chiếm 256 · 256 · 24 / 8 / 1024 = 192 KiB.