Dãy bítDo giới hạn của phần cứng máy tính, dữ liệutrong máy tính thường được biểu diễn bởi cácnhóm 8 bít [gọi là Byte]1 byte = 8 bit2 byte = 16 bit = 1 wordNgười ta có thể ghép nhiều byte hay nhiều wordđể tạo thành dãy bít dài hơn. Dãy bít càng dài thìlượng thông tin biểu diễn được càng lớn. Nếu gọiN là số bít của dãy thì số khả năng biểu diễn = 2NBộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 23 Dãy bítXét một dãy bít nhị phân:1 0msb010...00lsbBít đầu tiên [bên trái] được gọi là bít nặng nhấthay bít cao nhất của dãy [Most Significant Bit].Bít cuối cùng [bên phải] được gọi là bít nhẹ nhấthay bít thấp nhất của dãy [Least Significant Bit].Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 24 Số nguyên không dấuMột dãy bít sẽ tương ứng với một số nguyên lớnhơn hoặc bằng 0Ví dụ: Biểu diễn số nguyên 13 trong máy tính.Ở phần trước ta đã biết: số nguyên 13 chuyểnsang hệ nhị phân sẽ là 1101Trong máy tính sẽ có nhiều cách để biểu diễn sốnguyên này:+ Số nguyên dạng byte [8 bit]: 00001101+ Số nguyên dạng word [16 bit]: 00000000 00001101Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 25 Số nguyên có dấuMột dãy bít sẽ tương ứng với một số nguyên, cóthể âm hoặc dương.Khi biểu diễn dưới dạng nhị phân ta phải dànhra 1 bít để xác định dấu. Đó là bít đầu tiên củadãy [bít nặng nhất - Msb].+ Msb = 0: Dấu Dương+ Msb = 1: Dấu ÂmNhư vậy, nếu chiều dài dãy bít là 8 thì bít đầutiên để xác định dấu, 7 bít còn lại xác định giá trịsố nguyên?Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 26 Ví dụ:Số +13 được biểu diễn bởi dãy bít 0000 1101.Vậy số -13 được biểu diễn như thế nào, có phải là dãy bít1000 1101 hay không?Nguyên tắc để biểu diễn số âm trong máy tính: phải thoảmãn điều kiện sauSố Âm [nhị phân] + Số Dương [nhị phân] = 0Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 27 Giả sử số -13 được biểu diễn bởi dãy bít 1000 1101,ta đem nó cộng với dãy bít biểu diễn số +13 để kiểmtra:0000 1101+ 1000 11011001 1010≠ 0Ta thấy tổng thu được khác 0, như vậy đây khôngphải là dãy bít cần tìmBộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 28 Quy tắc tìm số đối:Cho 1 số nguyên A. Giả sử đã biết dãy bít biểu diễn A, khiđó muốn tìm dãy bít biểu diễn số -A ta làm như sau:Bước 1: Tìm số bù 1 của A bằng cách đảo tất cả các bít.Bước 2: Tìm số bù 2 [bằng cách lấy số bù 1 cộng với 1]Số bù 2 tìm được chính là dãy bít biểu diễn số -A.Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 29 Ví dụ 1:Xét A = 13 = 0000 1101Khi đó số bù 1 của A là 1111 0010Tìm số bù 2 [bằng cách lấy số bù 1 cộng với 1]1111 0010+11111 0011Như vậy -A = 1111 0011Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 30 Kiểm tra lại bằng cách cộng 2 dãy bít:0000 1101+ 1111 00111 0000 0000Kết quả thu được bằng 0 chứng tỏ ta đã tìm đúngVậy -13 = 1111 0011bBộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 31 Chứng minh:Số -1 trong máy tính ứng với một dãy toàn bít 1:-1 = 1111 1111bVì:Nên:Suy ra:A + A = −1A = − A −1− A = A +1Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 32 Ví dụ 2:Cho một dãy bít nhị phân sau đây [16 bit]:1110 0111 0001 1000bHãy xác định xem nó biểu diễn số nguyên nào?Bộ môn Kỹ thuật máy tính & mạng –Kiến trúc máy tính 2 - 33
Biểu diễn số nguyên trong máy tính
. Biểu diễn số nguyên
Số nguyên gồm số nguyên không dấu và số nguyên có dấu.
* Số nguyên không dấu là số không có bit dấu như 1 byte = 8 bit, có thể biểu diễn
* Số nguyên có dấu thể hiện trong máy tính ở dạng nhị phân là số dùng 1 bit làm bít dấu, người ta qui ước dùng bit ở hàng đầu tiên bên trái làm bit dấu [S]: 0 là số dương và 1 cho số âm. Ðơn vị chiều dài để chứa thay đổi từ 2 đến 4 bytes.
Ta thấy, với chiều dài 16 bit : bit đầu là bit dấu và 15 bit sau là bit số
Trị dương lớn nhất của dãy 2 bytes sẽ là:
Trị âm lớn nhất trong dãy 2 bytes là
Ðể thể hiện số âm trong hệ nhị phân ta có 2 khái niệm:
- Số bù 1: Khi đảo ngược tất cả các bit của dãy số nhị phân: 0 thành 1 và 1 thành 0, dãy số đảo đó gọi là số bù 1 của số nhị phân đó.
Ví dụ : N = 0101 = 5[10]
Số bù 1 của N là: 1010
- Số bù 2: Số bù 2 của số N là số đảo dấu của nó [-N]. Trong hệ nhị phân, số bù 2 được xác định bằng cách lấy số bù 1 của N rồi cộng thêm 1.
Ví dụ: N = 0101 = 5[10]
Số bù 1 của N là: 1010
+ 0001
Số bù 2 của N là: 1011 = -5[10] = -N
Kiểu số nguyên trên máy tính
Nhắc lại về hệ cơ số
Số \[X\] có biểu diễn là \[x_{n-1}x_{n-2} \dots x_0\] trong hệ cơ số \[B\], kí hiệu là \[[x_{n-1}x_{n-2} \dots x_0]_B\], thì \[X\] sẽ có giá trị:
\[X = x_{n-1}B^{n-1} + x_{n-2}B^{n-2} + \dots + X_0 B^0\]Ví dụ: \[[100]_2 = [4]_{10}\] [số 100 trong hệ 2 bằng với số 4 trong hệ 10].
Các hệ cơ số thường được dùng là 2, 8, 10, 16.
- Hệ nhị phân sử dụng các chữ số là 0 và 1
- Hệ bát phân sử dụng các chữ số từ 0 đến 7
- Hệ thập phân sử dụng các chữ số từ 0 đến 9
- Hệ thập lục phân sử dụng các chữ số từ 0 đến 9 và các chữ cái từ A đến F
Bạn có thể dùng tool chuyển đổi giữa các hệ cơ số ở /tools/numbase.
Hệ nhị phân
Trên máy tính, số nguyên được biểu diễn dưới dạng nhị phân, với số lượng chữ số cố định [fixed width integer]. Ví dụ, kiểu dữ liệu longint trên pascal lưu số nhị phân có 32 chữ số.
Vì vậy, khả năng lưu của mỗi kiểu dữ liệu sẽ bị giới hạn. Ví dụ, số nguyên không dấu 32 bit lưu được các số từ 0 đến \[2^{32} - 1\], tương đương 4294967295.
Ta có 2 khái niệm cần quan tâm:
- MSB: MSB là viết tắt cho “most significant bit”, nghĩa là bit có giá trị nhất. Đây là bit trái nhất của số.
- LSB: Là viết tắt của “least significant bit”, nghĩa là bit ít có giá trị nhất. Đây là bit phải nhất của số.
Các cách biểu diễn số âm
Ta cần một cách để biểu diễn số âm trong hệ nhị phân trên máy tính, cách được dùng hiện tại là số bù 2, tuy nhiên ta cũng sẽ lướt sơ qua những cách biểu diễn khác.
Số lượng dấu
Ở số lượng dấu, MSB được dùng làm bit lưu dấu, 0 là dương và 1 là âm, phần còn lại lưu giá trị của số. Ví dụ, -2 trong số nhị phân 8 bit sẽ có biểu diễn lượng dấu là \[10000010\].
Vấn đề của số lượng dấu là có 2 số 0 khác nhau: âm 0 và dương 0. Ngoài ra, các phép cộng trừ trên số lượng dấu cũng khá phức tạp vì phải xét dấu của số.
Số bù 1
Ở số bù 1, số dương được biểu diễn bình thường, còn số âm sẽ được lấy bù, nghĩa là đảo các bit lại. Ví dụ, xét số 8 bit, số 1 có biểu diễn là \[00000001\], nên -1 sẽ là \[11111110\].
Số bù 1 có lợi thế hơn số lượng dấu vì phép cộng trừ thực hiện bình thường không cần xét đến dấu của số, các số bị tràn ra sẽ được lược bỏ.
Tuy nhiên, số bù 1 vẫn có vấn đề vì có 2 biểu diễn của số 0: \[00000000\] và \[11111111\]. Để khắc phục việc này, người ta phát sinh ra số bù 2.
Số bù 2
Số âm của số bù 2 cũng được đảo bit lại [tương tự như số bù 1], sau đó cộng thêm 1 vào kết quả. Cụ thể, số 1 có biểu diễn \[00000001\], sau khi đảo bit là \[11111110\], ta tiếp tục cộng cho 1: \[11111111\]. Cuối cùng, biểu diễn của 1 trong số bù 2 [8 bit] là \[11111111\].
Như số lượng dấu và bù 1, số bù 2 cũng có số dương bắt đầu bằng 0, số âm bắt đầu bằng 1.
Tính giá trị của số lượng dấu:
\[x_{n-1}x_{n-2} \dots x_1 x_0 = -x_{n-1} 2^{n-1} + x_{n-2} 2^{n-2} + \dots + x_1 2^1 + x_0 2^0\]Ví dụ: \[11010110 = -2^7 + 2^6 + 2^4 + 2^2 + 2^1 = -42\]
Phạm vi biểu diễn của số bù 2 n-bit là từ \[-2^{n-1}\] [tương đương \[1000...00\]] đến \[2^{n-1}-1\] [tương đương \[0111...11\]].
Chuyển đổi kích thước số bù 2: Khi cần chuyển từ số bù 2 n-bit sang số bù 2 m-bit [ví dụ khi ép kiểu từ int sang long long], với \[m > n\] ta làm như sau:
- Các bit từ \[n+1\] đến \[m\] sẽ mang giá trị của MSB, nói cách khác, các bit thấp sẽ được giữ nguyên, các bit mới sẽ mang giá trị của MSB.
Số bias
Ngoài số bù 2, còn một kiểu nữa cũng được dùng trong máy tính là số bias. Số bias đơn giản là chọn một giá trị làm số 0, các biểu diễn nhỏ hơn sẽ là số âm, lớn hơn là số dương.
Giá trị bias cho số n-bit là \[2^{n-1} - 1\]. Ví dụ với số bias 8-bit, số 0 sẽ có biểu diễn là \[01111111\], số 1 là \[10000000\], -1 là \[01111110\].
Số bias dùng để lưu phần mũ trong kiểu số chấm động trên máy tính.
Các phép toán trên hệ nhị phân và ứng dụng
Phần này đi qua các phép toán như AND &, OR |, XOR ^, NOT ~, dịch trái trong C++.
Dịch trái
Kí hiệu: x > 2 = 00100000.
Một số điểm cần lưu ý:
- Không như dịch trái, dịch phải với số bit cần dịch lớn không gây Undefined Behavior.
- Dịch phải K bit tương đương với chia cho \[2^K\] [làm tròn xuống]. Cần chú ý việc làm tròn xuống, ví dụ 5 >> 1 = 2 nhưng -5 >> 1 = -3.
NOT
Phép NOT đảo từng bit của một số. Bit 0 sẽ thành 1 và 1 thành 0.
Trong C++ có 2 loại NOT là ! và ~. Phép ! xem đối số là kiểu bool [Đúng/Sai]. Còn phép ~ sẽ đảo từng bit của đối số. Ví dụ, xét kiểu số nhị phân 8-bit:
~00000010 [2] = 11111101 [-3 với kiểu có dấu; 253 với kiểu không dấu]
Tính số đối
Thay vì ghi -x, ta có thể thay bằng ~x + 1.
Tính x+1
Trong các vòng lặp, ta thường ghi i++. Tuy nhiên để hack não người đọc, ta có thể thay bằng i=-~i.
AND
Về cơ bản, phép AND cho kết quả là 1 khi và chỉ khi cả 2 số hạng là 1. Nếu coi 0 là sai và 1 là đúng thì có thể hiểu phép AND là “A AND B đúng khi cả A và B đều đúng”.
Trong C++ có 2 phép AND là & và &&.
&& xem 2 số hạng là kiểu bool [đúng/sai], còn & thực hiện tính toán trên từng bit của 2 số hạng:
110010 [50] & 011010 [26] ------ 010010 [18]
Như vậy ta có 50 & 26 = 16.
Đối với số âm, vì trên máy tính biểu diễn số âm bằng kiểu bù 2 nên kết quả sẽ khác số dương:
11111110 [-2] & 00000111 [7] -------- 00000110 [6]
Như vậy ta có -2 & 7 = 6.
Giới thiệu bảng chân trị
Bảng chân trị cho phép định nghĩa các phép toán logic. Bảng chân trị của phép AND là:
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Tính MOD [số dư]
Khi cần tính số dư khi chia cho M, với M là lũy thừa của 2 ta có thể thay x % M bằng x & [M-1]. Ví dụ:
x % 8 => x & 7 x % 4 => x & 3 x % 2 => x & 1
Trong máy tính, AND được thực hiện nhanh hơn rất nhiều so với phép MOD, ta nên dùng AND khi có thể.
Lấy giá trị của bit
Xét một bit x, ta thấy x AND 1 = x. Từ nhận xét này, có thể dùng AND để lấy giá trị của bit bất kì trong một số. Ví dụ:
- Lấy giá trị bit thứ k của x: x & [1