Trong toán học, các số âm [bất kể thuộc hệ cơ số nào] đều được biểu diễn bằng cách thông thường là đặt trước số dương tương ứng một dấu "−" [trừ]. Ví dụ: với hệ thập phân, số nguyên âm năm được biểu diễn là −5. Tuy nhiên, trong máy tính, khi mọi ký hiệu, con số,... đều được biểu diễn dưới hệ nhị phân thông qua hai chữ số 0 và 1 thì mọi chuyện lại trở nên phức tạp hơn.
Có nhiều cách được sử dụng để biểu diễn số âm trong máy tính. Bài này chỉ giới thiệu bốn phương pháp chủ yếu nhất, đó là: phương pháp dấu lượng [sign-and-magnitude], bù 1, bù 2 và số quá N [excess-N].
Các máy tính hiện nay hầu hết đều sử dụng phương pháp biểu diễn số bù 2. Tuy nhiên, trong vài tình huống, các phương pháp khác vẫn có thể được sử dụng.
Phương pháp dấu lượng dùng bit cực trái làm bit dấu [sign bit] – tức đại diện cho dấu của số – theo quy ước: nếu bit dấu là 1 thì số là số âm [1 tương đương với dấu "-"], ngược lại, nếu nó là 0 thì số là số dương [0 tương đương với dấu "+"]. Các bit còn lại được dùng để biểu diễn độ lớn của số [hay giá trị tuyệt đối – absolute value – của số].
Để biểu diễn một số âm về dạng nhị phân có dấu với mẩu K bit là lấy số cần biểu diễn cộng thêm 2K-1 sau đó biểu diễn chúng ở hệ nhị phân
Theo phương pháp này, một byte 8 bit sẽ có 7 bit [trừ đi bit dấu] được dùng để biểu diễn cho các số có giá trị từ 0000000 [010] đến 1111111 [12710]. Khi sử dụng bit dấu, ý nghĩa của 7 bit trên sẽ thay đổi, và ta có thể biểu diễn các số từ −12710 đến +12710. Trong phương pháp dấu lượng, số 0 có thể được biểu diễn ở hai dạng, đó là 00000000 [+0] và 10000000 [−0].
Ví dụ: giả sử mẫu 8 bit, khi sử dụng phương pháp dấu lượng, số 510 được biểu diễn sang hệ nhị phân là: 0000 0101, còn số −5 là 1000 0101.
So sánh với cách biểu diễn số âm mà ta thường sử dụng, ta thấy phương pháp dấu lượng có nhiều điểm tương đồng. Trong hệ thập phân, khi muốn biểu diễn số có dấu, ta đặt dấu cần biểu diễn ngay trước giá trị tuyệt đối của số. Phương pháp dấu lượng cũng đặt dấu ngay trước giá trị tuyệt đối của số, chỉ có khác ở chỗ thay dấu "+" bằng "0" và "−" bằng "1". Có lẽ vì sự tương đồng này, một vài máy tính thế hệ đầu tiên [như IBM 7090] đã sử dụng phương pháp dấu lượng khi biểu diễn số âm.
Bài chi tiết: Bù 1
Phương pháp bù 1 biểu diễn số âm theo cách sau:
- Thứ nhất, bit dấu 0 nếu số là số dương, và 1 nếu số là số âm.
- Thứ hai, sử dụng toán tử thao tác bit [bitwise] NOT để đảo tất cả các bit của số nhị phân dương [tính bit dấu] để biểu diễn số âm tương ứng.
Như vậy, phương pháp bù 1 hoàn toàn giống như phương phá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] [xem bài chính về bù 1 để biết cách biểu diễn số thập phân sang nhị phân bằng phương pháp bù 1].
Giống phương pháp dấu lượng, một byte 8 bit áp dụng phương pháp bù 1 cũng có thể biểu diễn các số từ −12710 đến +12710 [chú ý: đã mất đi một bit dùng làm bit dấu]. Bù 1 cũng có hai dạng biểu diễn cho số 0, bao gồm: 00000000 [+0] và 11111111 [−0] [mẫu 8 bit].
Khi thực hiện phép cộng giữa hai số biểu diễn theo phương pháp bù 1, ta cũng thực hiện theo quy tắc cộng nhị phân thông thường, tuy nhiên, sau khi đã thực hiện xong, nếu còn phát sinh bit nhớ thì phải tiếp tục cộng bit nhớ này vào kết quả vừa thu được. Về vấn đề này, xin xem thêm ở bài chính về bù 1.
Phương pháp biểu diễn số bù 1 được sử dụng rộng rãi trong các thế hệ máy tính cũ, điển hình là các dòng máy PDP-1 và UNIVAC 1100/2200.
Bài chi tiết: Bù 2
Trong phương pháp bù 2, các số âm được biểu diễn giống như phương pháp bù 1, tuy nhiên, phải cộng thêm 1 vào kết quả [ở hệ nhị phân].
Ví dụ: số −510 được biểu diễn sang hệ nhị phân [xét mẫu 8 bit] sử dụng phương pháp bù 1 là 11111010. Để biểu diễn theo phương pháp bù 2, ta cộng thêm 1 vào số nhị phân ở bù 1, tức cộng 1 cho 11111010: 11111010 + 1 = 11111011. Vậy 11111011 là biểu diễn bằng bù 2 của −510 trong máy tính.
Phương pháp biểu diễn số bù 2 ra đời khi người ta gặp vấn đề với hai phương pháp dấu lượng và bù 1, đó là:
- Có hai cách biểu diễn cho số 0.
- Bit nhớ phát sinh sau khi đã thực hiện phép tính phải được cộng tiếp vào kết quả.
Với phương pháp bù 2, số 0 chỉ có một cách biểu diễn duy nhất là 00000000 [mẫu 8 bit]. Việc đổi dấu một số – kể cả từ âm sang dương hay từ dương sang âm – đều được thực hiện theo cùng một cách, đó là: đảo tất cả các bit rồi cộng thêm một vào kết quả. Việc thực hiện phép cộng với số biểu diễn theo phương pháp bù 2 được thực hiện hoàn toàn giống như cộng hai số nhị phân bình thường, tuy nhiên, khi phát sinh bit nhớ ở bit dấu, ta có thể bỏ nó đi. Về vấn đề này, xin xem thêm ở bài chính về bù 2.
Với mẫu 8 bit, phương pháp bù 2 có thể biểu diễn tốt các số nguyên có giá trị từ −12810 đến +12710 [so với từ −12710 đến +12710 theo phương pháp dấu lượng và bù 1] do được lợi từ việc tiết kiệm được một cách biểu diễn số 0 [không phân biệt giữa −0 và +0].
Bài chi tiết: Bài chính về Số quá N [với trường hợp N = 3]
Phương pháp biểu diễn số quá N – còn được gọi là biểu diễn số dịch [biased representation] – sử dụng một số nguyên N cho trước làm giá trị dịch ["dịch" hiểu nôm na theo nghĩa "sự dịch chuyển" hay "sự thiên lệch"]. Theo phương pháp này, một giá trị thập phân [tức giá trị cần biểu diễn] sẽ được biểu diễn bằng dạng nhị phân của một số dương nào đó sao cho, giá trị của số dương này lớn hơn giá trị cần biểu diễn N đơn vị.
Ví dụ: giả sử cần biểu diễn giá trị 210 theo số quá 5 [mẫu 8 bit]:
- Bước 1: ta có:
- Giá trị cần biểu diễn: 2.
- N = 5.
- Bước 2: xác định số dương lớn hơn 210 năm đơn vị, đó là số 7.
Vậy 210 sẽ được biểu diễn bằng dạng nhị phân của 7: 00000111.
Theo ví dụ trên, ta sẽ có bảng sau:
| −5 | 0 | 00000000 |
| −4 | 1 | 00000001 |
| −3 | 2 | 00000010 |
| −2 | 3 | 00000011 |
| −1 | 4 | 00000100 |
| 0 | 5 | 00000101 |
| 1 | 6 | 00000110 |
| 2 | 7 | 00000111 |
| 3 | 8 | 00001000 |
| 4 | 9 | 00001001 |
| 5 | 10 | 00001010 |
| 6 | 11 | 00001011 |
| 7 | 12 | 00001100 |
| 8 | 13 | 00001101 |
| 9 | 14 | 00001110 |
| 10 | 15 | 00001111 |
Ta thấy, 0 được biểu diễn bằng nhị phân của 5, và −5 được biểu diễn bằng nhị phân của 0. Tổng quát, 0 được biểu diễn bằng nhị phân của N, còn −N được biểu diễn bằng mẫu có tất cả các bit đều là 0.
Phương pháp này ngày nay còn được sử dụng rộng rãi để biểu diễn các số chấm động [floating point number], tiêu biểu là chuẩn số chấm động IEEE. Theo chuẩn này, các số chấm động có độ chính xác đơn [single-precision] 32 bit [như kiểu float của Java] có phần mũ [chính là số lượng ký số của phần nằm sau dấu chấm thập phân] được biểu diễn bằng số quá 127 với mẫu 8 bit, và các số chấm động có độ chính xác đôi [double-precision] 64 bit [như kiểu double của Java] có phần mũ biểu diễn bằng số quá 1023 với mẫu 11 bit.
- Bù 1
- Bù 2
- Số quá 3
Lấy từ “//vi.wikipedia.org/w/index.php?title=Biểu_diễn_số_âm&oldid=68131026”
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