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