Cách biểu diễn số nguyên ở hệ 2
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 Show
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.
Bạn có thể dùng tool chuyển đổi giữa các hệ cơ số ở /tools/numbase. Hệ nhị phânTrê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:
Các cách biểu diễn số âmTa 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ù 2Số â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:
Số biasNgoà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ụngPhần này đi qua các phép toán như AND &, OR |, XOR ^, NOT ~, dịch trái <<, dịch phải >> trong C++. Dịch tráiKí hiệu: x << k. Ý nghĩa là dịch các bit của x sang trái k đơn vị. Các bit bị dư ra sẽ bị mất, các bit mới được gán bằng 0. Ví dụ đối với số nhị phân 8-bit: 00000101 << 2 = 00010100 00001000 << 4 = 10000000 10100111 << 3 = 00111000 00000000 << k = 00000000 Một số điểm cần lưu ý:
Dịch phảiDịch phải ngược lại với dịch trái, là dịch bit sang bên phải. Kí hiệu: x >> k. Có 2 loại dịch phải là logical và arithmetic. Phép dịch phải trong C++ thuộc loại arithmetic, các bit mới thêm vào ở phía bên trái sẽ được gán bằng bit dấu, gán bằng 0 khi dịch với kiểu số không dấu. Ví dụ:
Một số điểm cần lưu ý:
NOTPhé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ố đốiThay vì ghi -x, ta có thể thay bằng ~x + 1. Tính x+1Trong 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. ANDVề 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à:
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 bitXé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ụ:
Tắt bit tại vị trí bất kìTắt bit có nghĩa là gán bit tại vị trí đó bằng 0. Ta thấy x & 0 = 0, nên có thể dùng AND để tắt bit. Giả sử cần tắt bit K trong số X. Ta thực hiện AND X với số MASK thỏa:
Ví dụ, để tắt bit thứ 0, dùng x & -2. Kết hợp với phép NOT, ta có thể tạo ra MASK để tắt bit tại vị trí K: X & ~(1 << K) Tìm bit thấp nhất khác 0Đây chính là thao tác cơ bản nhất của cây Fenwick. Để cho ngắn gọn ta kí hiệu “bit thấp nhất khác 0” của x là F(x). Một số ví dụ:
Công thức: F(x) = x & -x Phép tính này tận dụng cách biểu diễn bù 2 để tính toán. Để hiểu rõ, bạn đọc nên tính tay trên giấy. Duyệt tất cả các tập conTrong các bài toán duyệt, ta thường dùng số nhị phân để biểu diễn việc chọn/không chọn một phần tử. Ví dụ, số 13 có biểu diễn nhị phân là 1101, nên 13 đại diện cho một tập hợp chứa 3 số là 0, 2, 3. Làm thế nào khi ta cần xét tất cả các tập con của 13: 1100, 1001, 0101, 0001,…? Việc này được thực hiện nhanh bằng phép AND như sau: #include Đoạn code ở trên dùng std::bitset để in ra biểu diễn nhị phân của k. Có một điều lạ là cả printf và cout đều không hỗ trợ việc in ra biểu diễn nhị phân của số. OROR cho kết quả là đúng khi có ít nhất 1 trong 2 số hạng là đúng. Bảng chân trị:
Kí hiệu phép OR trong C++: x | y. Tương tự với AND, C++ cũng có 2 loại OR là | và ||. Bật bitBật bit có nghĩa là gán bit tại vị trí đó bằng 1. Xét bit x, ta thấy x OR 1 = 1 và x OR 0 = x. Vì vậy có thể dùng OR để bật bit bất kì lên. Để bật bit thứ K trong số X: X | (1 << K) Phép XORXOR cho kết quả là đúng khi 2 số hạng là khác nhau. Bảng chân trị:
Phép XOR trong C++: x ^ y Gán một số bằng 0Ta thấy x XOR x = 0, nên khi lập trình, thay vì ghi x = 0, ta có thể thay bằng x = x ^ x. Trong thực tế thì khi dịch ra mã máy, x = 0 sẽ được trình dịch chuyển thành x = x ^ x. Đảo bit tại một vị trí bất kìCó nghĩa là nếu bit tại vị trí đó đang là 1 thì ta gán bằng 0, đang là 0 thì ta gán bằng 1. Cách làm hoàn toàn tương tự như việc bật/tắt bit ở trên. Ta thấy x XOR 0 = 0 và x XOR 1 = NOT x, vì vậy để đảo bit tại vị trí K của số X, dùng: X ^ (1 << K). Kham khảo thêmBạn đọc có thể kham khảo thêm ứng dụng của các phép toán nhị phân ở: |