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ị:

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:

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 <<, dịch phải >> trong C++.

Dịch trái

Kí 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 ý:

• Sử dụng dịch trái cho số âm là một việc làm nguy hiểm. Kể từ C++11, đây là Undefined Behavior.
• Khi không xảy ra tràn số, dịch trái K bit tương đương với nhân cho \(2^K\).
• Dịch trái với số bit cần dịch quá lớn sẽ gây ra Undefined Behavior. Cụ thể, với kiểu số nguyên K bit thì số bit có thể dịch tối đa là K-1.

Dịch phải

Dị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ụ:

• Với kiểu số có dấu 8-bit, 10000000 >> 2 = 11100000.
• Với kiểu số không dấu 8-bit, 10000000 >> 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à:

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 << k)
• Lấy giá trị 4 bit cuối cùng của x: x & 15

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:

• Bit ở vị trí K bằng 0
• Tất cả các bit còn lại bằng 1

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ụ:

• F(100) = 4, 100 có biểu diễn nhị phân là 1100100, bit thấp nhất khác 0 là 100 có giá trị là 4.
• F(64) = 64, mở rộng hơn, F(x) = x khi x là lũy thừa của 2.
• F(số lẻ) = 1, do số lẻ luôn có bit thấp nhất = 1.

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 con

Trong 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 <bitset>
#include <iostream>
using namespace std;

int main() {
    int x = 13;
    for (int k = x; k > 0; k = (k-1) & x) {
        cout << bitset<4>(k) << '\n';
    }
}

Đ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ố.

OR

OR 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 bit

Bậ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 XOR

XOR 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 0

Ta 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êm

Bạn đọc có thể kham khảo thêm ứng dụng của các phép toán nhị phân ở:

• http://graphics.stanford.edu/~seander/bithacks.html
• http://bits.stephan-brumme.com/