Trong các ngôn ngữ lập trình, kiểu số nguyên thường bị giới hạn ở 1 mức độ nhất định. Ví dụ với kiểu dữ liệu int trong ngôn ngữ C++ giới hạn ở mức 2,147,483,648 đến 2,147,483,647. Tuy nhiên trong một số trường hợp cần phải thác tác với những số liệu vượt quá mức giới hạn này.
Bài viết sẽ hướng dẫn thiết kế kiểu dữ liệu QInt có độ lớn 16 bytes và hiện thực toán tử nhân chia trên nó.
Ý tưởng
Với ngôn ngữ C++, kiểu số nguyên có phạm vi lớn nhất là 4 bytes (unsigned int) nên không thể đáp ứng được yêu cầu. Do đó phải thiết kế riêng 1 kiểu cấu trúc mới để lưu trữ dữ liệu với phạm vi 16 bytes, tương đương 128 bits.
Xây dựng cấu trúc dữ liệu gọi là QInt, được tạo từ 1 mảng 4 phần tử thuộc kiểu dữ liệu unsigned int.
Với mỗi phần tử kiểu unsigned int gồm 4 bytes. Mỗi bytes là 8 bits. Vậy từ 4 phần tử unsigned int, được 16 bytes hay 128 bits nhớ lưu trữ.
Chuẩn bị
Xây dựng 1 class QInt có thuộc tính là 4 biến unsigned int tương ứng với 4 phần của 128 bits.
struct QInt{
unsigned int mask[4];
}
Với mỗi chuỗi số ở hệ thập phân nhập vào, chuyển đổi sang hệ nhị phân. Ghi giá trị bit lên struct đã thiết lập.
Công thức tính vị trí
Gọi an là bit thứ n trong QInt.
Bit an là bit thứ n%32 của mask[n/32].
Ví dụ: Bit a33 là bit 1 của mask[1].
Công thức bitmask
Áp dụng công thức bật bit thứ i của n: n = (1 << i) | n
Ví dụ: Bật bit a33 của QInt: (1 << (33 % 32)) | mask[33/32]
Mọi thao tác với QInt đều được thực hiện ở hệ nhị phân, đã được lưu trong mask.
Phạm vi biểu diễn
-2127 đến 2127-1
Hiện thực
Bước 1. Khởi tạo
Khởi tạo giá trị mảng mask bằng 0.
qint::qint()
{
mask[0] = mask[1] = mask[2] = mask[3] = 0;
}
Bước 2. Đọc dữ liệu
Đọc dữ liệu đầu vào với kiểu dữ liệu String dạng thập phân.
Số âm
Chuyển đổi số nguyên âm hệ thập phân sang hệ nhị phân theo bước như sau:
if (dec[0] == '-') //So am
{
dec.erase(0, 1); //Coi nhu bo di dau tru
bin = decToBin(dec); //Chuyen doi du lieu sang he 2
bin = twoComplement(bin); //Chuyen sang dang bu 2
}
Loại bỏ dấu - đầu chuỗi
Dùng hàm erase để loại bỏ 1 kí tự - tại vị trí 0 của chuỗi nhập vào.
dec.erase(0, 1);
Chuyển đổi số sang hệ nhị phân
string decToBin(string s)
{
stringtemp = delBeginZero(s);
stringresult = "";
char q = strMod2(temp) + '0';
result = q + result;
temp = strDiv2(temp);
while (temp != "0")
{
char t = strMod2(temp) + '0';
result = t + result;
temp = strDiv2(temp);
}
return result;
}
Chuyển đổi số sang dạng bù 2
string twoComplement(string a)
{
while (a.size() < 128) a = "0" + a;
string result = a;
bool flag = false;
for (int i = result.size() - 1; i > 0 && flag != true; i--)
{
if (result[i] == '1')
{
for (int j = i - 1; j > 0; j--)
result[j] = (result[j] == '0') ? '1' : '0';
flag = true;
}
}
result[0] = '1';
return result;
}
Số dương
Chuyển đổi số nguyên dương sang số nhị phân như sau:
Chuyển đổi số chuỗi dữ liệu nhập sang nhị phân
bin = decToBin(dec); //Chuyen sang he 2
Bổ sung các chữ số 0 vào đầu chuỗi cho đủ độ dài 128 bits
unsigned int len = bin.size();
for (unsignedinti = 0; i < 128 - len; i++)
{
bin = "0" + bin;
}
Đảo chuỗi
void reverse(string &s) //Dao chuoi
{
int i = 0, j = s.length() - 1;
while (i < j)
{
swap(s[i], s[j]);
i++; j--;
}
}
Ghi dữ liệu vào struct QInt
for (unsigned int i = 0; i < bin.size(); i++) //Doc du lieu vao struct qint
{
if (bin[i] == '1')
{
mask[i / 32] = (1 << (i % 32)) | mask[i / 32];
}
}
Bước 3. Hiện thực toán tử nhân 2 số
Thuật toán Booth
Thuật toán Booth được Andrew Donald Booth phát minh vào năm 1950 dùng để nhân 2 số nhị phân có dấu ở dạng bù 2.
- Các số hạng trong phép nhân phải có dấu.
- Các số hạng có độ dài bit giống nhau.
- Khởi tạo Q-1 = 0
- Khi Q0Q1 = 00 hay 11 dời bit sang phải giảm số hạng nhân là 1.
- Khi Q0Q1 = 01 thì A = A+M dời bit sang phải giảm số hạng nhân là 1.
- Khi Q0Q1 = 10 thì A = A-M dời bit sang phải giảm số hạng nhân là 1.
- Khi dời bit giữ dấu của A.
- Khi nhân hết số hạng kết quả là giá trị được nối giữa 2 giá trị A và Q
Code
qint qint::operator*(const qint &b)
{
qint q = *this;
qint m = b;
if (((m.mask[3] >> 31) & 1) == 1 && ((q.mask[3] >> 31) & 1) == 1)
{
qint t0;
m = t0 - m;
q = t0 - q;
}
qint temp;
temp.Init();
unsigned int q1 = 0, k = 128;
while (k > 0)
{
if ((q.mask[0] & 1) == 1 && q1 == 0)
temp = temp - m;
else
if ((q.mask[0] & 1) == 0 && q1 == 1)
temp = temp + m;
q1 = q.mask[0] & 1;
q = q >> 1;
if ((temp.mask[0] & 1) == 0)
q.mask[3] = q.mask[3] & (~((unsignedint)1 << 31));
else
q.mask[3] = q.mask[3] | ((unsignedint)1 << 31);
temp = temp >> 1;
k--;
}
string ans = temp.toBin() + q.toBin();
supporter *s = newsupporter;
s->reverse(ans);
temp.mask[0] = temp.mask[1] = temp.mask[2] = temp.mask[3] = 0;
for (inti = 0; i < 128; i++) //Doc du lieu vao struct qint
{
if (ans[i] == '1')
{
temp.mask[i / 32] = temp.mask[i / 32] | ((unsignedint)1 << (i % 32));
}
}
return temp;
}
Bước 4. Hiện thực toán tử chia 2 số
Chuyển đổi số bị chia và số chia về dạng số dương.
if (((q.mask[3] >> 31) & 1) == 1)
{
qint t0;
q = t0 - q;
negative = !negative;
}
if (((m.mask[3] >> 31) & 1) == 1)
{
qint t0;
m = t0 - m;
negative = !negative;
}
Sử dụng thuật giải chia số nguyên không dấu.
Kết quả thương trong Q và phần dư trong A.
qint temp;
unsigned int k = 128;
while (k > 0)
{
temp = temp << 1;
if (((q.mask[3] >> 31) & 1) == 1)
temp.mask[0] = temp.mask[0] | 1;
else
temp.mask[0] = temp.mask[0] & (~(unsigned int)1);
q = q << 1;
temp = temp - m;
if (((temp.mask[3] >> 31) & 1) == 1)
{
q.mask[0] = q.mask[0] & (~(unsigned int)1);
temp = temp + m;
}
else
q.mask[0] = q.mask[0] | 1;
k--;
}
Hiệu chỉnh dấu của kết quả.
| Số bị chia | Số chia | Số thương | Số dư |
| + | + | Giữ nguyên kết quả | Giữ nguyên kết quả |
| + | - | Đảo dấu kết quả | Giữ nguyên kết quả |
| - | + | Đảo dấu kết quả | Đảo dấu kết quả |
| - | - | Giữ nguyên kết quả | Đảo dấu kết quả |
if (negative)
{
qint t0;
q = t0-q;
}
Code
qint qint::operator/(const qint &b)
{
qint q = *this;
qint m = b;
bool negative = false;
if (((q.mask[3] >> 31) & 1) == 1)
{
qint t0;
q = t0 - q;
negative = !negative;
}
if (((m.mask[3] >> 31) & 1) == 1)
{
qint t0;
m = t0 - m;
negative = !negative;
}
qint temp;
unsigned int k = 128;
while (k > 0)
{
temp = temp << 1;
if (((q.mask[3] >> 31) & 1) == 1)
temp.mask[0] = temp.mask[0] | 1;
else
temp.mask[0] = temp.mask[0] & (~(unsigned int)1);
q = q << 1;
temp = temp - m;
if (((temp.mask[3] >> 31) & 1) == 1)
{
q.mask[0] = q.mask[0] & (~(unsigned int)1);
temp = temp + m;
}
else
q.mask[0] = q.mask[0] | 1;
k--;
}
if (negative)
{
qint t0;
q = t0-q;
}
return q;
}
