Biểu diễn số nguyên có dấuPhương pháp lượng dấu: Ta có thể biểu diễn cácsố từ −12710 đến +12710. Phương pháp này làmcho số âm lẫn trị tuyệt đối của nó [như −5 với+5] đều được biểu diễn theo cùng một cách ở 7bit biểu diễn độ lớn Ví dụ: Số 5 được biểu diễn sang hệ nhị phân là:00000101, còn số −5 là 10000101. Biểu diễn số nguyên có dấuPhương pháp bù 1: Sử dụng toán tử thao tác bitNOT để đảo tất cả các bit của số nhị phân dương[dĩ nhiên không tính bit dấu] để biểu diễn số âmtương ứng. Phương pháp bù 1 hoàn toàn giống như phươngpháp dấu lượng, duy chỉ khác ở cách biểu diễnđộ lớn của số Ví dụ: Dạng bù 1 của 00101011 [43] là11010100[−43]. Phương pháp bù 2: Một số bù 2 có được do đảo tấtcả các bit có trong số nhị phân [đổi 1 thành 0 vàngược lại] rồi thêm 1 vào kết quả vừa đạt được. Thựcchất, số biểu diễn ở dạng bù 2 là số biểu diễn ở bù 1rồi sau đó cộng thêm 1. Trong quá trình tính toánbằng tay cho nhanh người ta thường sử dụng cáchsau: từ phải qua trái giữ 1 đầu tiên và các số còn lạibên trái số 1 lấy đảo lại [chỉ áp dụng cho số có bit cựcphải là 1]. Phương pháp bù 2 thường được sử dụng đểbiểu diễn số âm trong máy tính. Theo phương phápnày, bit cực trái [là bit nằm bên trái cùng của byte]được sử dụng làm bit dấu [sign bit - là bit tượng trưngcho dấu của số] với quy ước: nếu bit dấu là 0 thì số làsố dương, còn nếu nó là 1 thì số là số âm. Ngoài bitdấu này ra, các bit còn lại được dùng để diểu diễn độlớn của số. Ví dụ: số nguyên −5 ở hệ thập phân được biểu diễntrong máy tính theo phương pháp bù 2 như sau [vớimẫu 8 bit]: Bước 1: xác định số nguyên 5 ở hệ thập phân đượcbiểu diễn trong máy tính là: 0000 0101. Bước 2: đảo tất cả các bit nhận được ở bước 1. Kếtquả sau khi đảo là: 1111 1010. Bước 3: cộng thêm 1 vào kết quả thu được ở bước 2:kết quả sau khi cộng: 1111 1011. Bước 4: vì là biểu diễn số âm nên bit bên trái cùngluôn giữ là 1. Vậy với phương pháp bù 2, số −5 ở hệ thập phânđược biểu diễn trong máy tính như sau: 1111 1011. Biểu diễn số thực Số thực được biểu diễn dưới dạng IEEE 754 có độchính xác đơn [được biểu diễn bằng 32 bit – 1 bit dấu– 8 bit mũ – 23 bit giá trị phần lẻ] và độ chính xáckép [được biểu diễn bằng 64 bit – 1 bit dấu – 11 bitmũ – 52 bit giá trị phần lẻ]. Để có thể lưu được sốthực dưới dạng IEEE 754, chúng ta cần phải chuyểnsố chúng ta cần lưu về dạng số thực chuẩn[ số thựcchuẩn là số mà phần nguyên không có chứa số 0]. Ví dụ: Biểu diễn số -3.56125 trong máy tính:Bước 1: Chuyển phần nguyên sang hệ nhị phânBước 2: Chuyển số ở phần lẻ sang hệ nhị phân Nhân số 0.56125 cho 223 [đối với độ chính xác kép là252] = 4708106 Lấy kết quả vừa tính ra được trừ lần lượt cho 222 [đốivới độ chính xác kép là 252] đến 20 Nếu trừ cho 2n mà kết quả < 0 thì bỏ qua, ngược lạithì sẽ tiếp tục thực hiện phép trừ. Ngừng thực hiệnphép trừ khi kết quả ra bằng 0
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