Báo cáo Bài Tập Số 1: Biểu Diễn và Tính Toán Số Nguyên môn Hệ thống máy tính | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

lOMoAR cPSD| 59994889
Môn học: Hệ thống Máy tính
BÁO CÁO BÀI TẬP SỐ 1
Biểu diễn và tính toán số nguyên
1.Thông tin sinh viên thực hiện ST T MSSV Họ và tên Email 1 2312007 Nguyễn Văn Phước nguyenvanphuoc1172@gmail.c om 4
2.Đánh giá mức độ hoàn thành đồ án.
Điểm tự đánh giá: 10/10 Bài Đặc điểm Mức độ hoàn Ghi chú thành 1
1.1: Nhập vào số nguyên X (4 100% - Viết được hàm
bytes) có dấu. Đọc dãy nhị phân string
của X và xuất ra màn hình dec2Bin(int) cùng các hàm phụ trợ để “đọc” dãy nhị phân của một số nguyên X
1.2: Cho mảng một chiều A gồm 100% 100% - Viết được hàm long
32 phần tử là các số 0 hoặc 1. Xây long bin2Dec(int*,
dựng số nguyên X 4 bytes có các (int*)int*,int size = 32) cùng các
bit giống với các phần tử mảng A,
hàm phụ trợ để “đọc”
sau đó xuất X ra màn hình dãy nhị phân của một số nguyên X 1 lOMoAR cPSD| 59994889 2
Viết chương trình nhập vào hai 100% - Xây dựng cấu trúc
dãy bit 8 bit (ở dạng bù 2) Bits để thuận tiện
Thực hiện các phép tính cộng, cho việc đọc và
trừ, nhân, chia trên hai dãy bit đã thực hiện phép
nhập theo các thuật toán đã học tính - Thực hiện được các phép tính cộng, trừ, nhân, chia hay dãy bit ( hai biến kiểu Bits ) Riêng phép chia có sử dụng thủ thuật
để cho ra đúng kết quả theo bù 2
3.Thông số kĩ thuật của môi trường phát triển - Môi trường phát triển:
o Hệ điều hành: Windows 11 24H2
o Môi trường phát triển: Visual Studio Code 1.98.1
o Ngôn ngữ được dùng: C++ 14 o Trình biên dịch: MinGW 6.3.0 - Lưu ý:
o Hệ điều hành: Sử dụng Windows 11 (có thể sử dụng Windows 10 hoặc thấp hơn)
o Môi trường phát triển: Có thể sử dụng các môi trường sau:
Visual Studio Code (tốt nhất nên sử dụng bản 1.98.1 trở lên).
Một số gợi ý khác như:
• DevC++ (Embarcadero 6.3) hoặc hơn
• Visual Studio 2022 Community (trình biên dịch MSVC 14.40,
tuy nhiên cần chỉnh sửa một cút trong code)
o Ngôn ngữ: C++ 14 (có thể sử dụng C++ 14 hoặc hơn)
4.Mô tả về các cấu trúc dữ liệu, hàm được sử dụng 4.1. Câu 1.1 4.1.1. Hàm chính string dec2Bin(int number) { string res = "";
for (int i = 31; i >= 0; i--) {
res += ((number >> i) & 1) ? "1" : "0"; } return res; 2 lOMoAR cPSD| 59994889 }
Hàm này có tác dụng chuyển từ số thập phân sang số nhị phân. Bằng cách lấy
bit cuối cùng của số khi dịch phải k lần, sau đó gán lần lượt vào một chuỗi rỗng,
ta sẽ có kết quả trả ra là dãy nhị phân 32-bit của số đó (lặp với chỉ số i từ 0 →31).
Trong vòng lặp trên, câu lệnh được hiểu như sau: Nếu sau khi dịch bit k lần, sau
đó thực hiện AND với 1, nếu còn lại 32 bit 0 (tức là số 0, hay false theo toán tử
điều kiện) sẽ trả về chuỗi kí tự “0”, ngược lại sẽ trả về “1”
Thực chất có thể thay thể bằng cấu lệnh:
res += to_string((number >> i) & 1);
Vì căn bản câu lệnh (number >> i) & 1) dùng để dịch bit và chuyển số vừa dịch bit
về hệ số thập phân, nên ta có thể thực hiện to_string tùy ý
Việc thực hiện câu lệnh này giống với việc thực hiện chia số cho 2 và chỉ lấy phần
dư, cho số đến khi không thể chia được nữa (tức số bị chia bằng 0), sau đó thực
hiện viết ngược lại các số dư từ dưới lên. 4.1.2. Hàm phụ trợ
Căn bản thì hàm này không cần có hàm phụ trợ. Bản thân hàm này đã thực hiện
đúng chức năng mà không cần phải quá phức tạp ở thân hàm
void printString(const string &str) {
for (int i = 0; i < str.size(); i++) { cout << str[i];
if ((i + 1) % 8 == 0 && i < str.size() - 1) cout << " "; } cout << endl; }
Hàm phụ trợ duy nhất đi kèm chính là hàm in chuỗi nhị phân: thực hiện in từng kí
tự và in dấu cách nếu in đủ 8 kí tự mỗi lần 4.2. Câu 1.2 4.2.1. Hàm chính
long long bin2Dec(int* bitArray, int (*signFunc)(int*), int size = 32) { long long result = 0;
for (int i = 0; i < size; i++) {
result = (result << 1) + bitArray[ i]; }
if (signFunc == signedInteger && bitArray[0] == 1) {
result -= (1LL << size) ; } 3 lOMoAR cPSD| 59994889 return result; }
Hàm này có tác dụng chuyển đổi số nhị phân thành số thập phân. Danh sách tham số
đầu vào của hàm này bao gồm: Một con trỏ chỉ đến một mảng số 32 phần tử (không
có kiểm tra đầu vào), một con trỏ hàm để thực hiện trả về một hàm thực hiện việc
chuyển đổi không dấu hay có dấu, và một biến size mặc định giá trị là 32.
Quá trình thực hiện: Khai báo một biến kết quả, qua một vòng lặp thì cứ cộng dần
(result << 1) + bitArray[i]; (kỹ thuật cơ bản để xử lý bit mà không cần
dùng đến pow(2, n), mất thời gian và giảm nguy cơ mất dữ liệu khi chuyển đổi từ double (float) sang int)
Khi thực hiện xong, nếu con trỏ hàm được gán giá trị là signedInteger (tức hàm
trả về thông báo đầu ra là số có dấu) thì thực hiện trừ đi cho 2^size (MSB là bit
thứ 32) hay 1 ≪ size (size = 32).
Căn bản thì nếu thực hiện chuyển đổi số dưới 2^31 (tức bitArray[0] == 0) thì cả hai
đều giống nhau. Nếu chuyển đổi từ 2^31 trở lên (tức bitArray[0] == 1) thì sẽ có sự khác biệt. 4.2.2. Hàm phụ trợ
int signedInteger(int* array) {
return (array[0] == 0) ? 0 : 1; }
int unsignedInteger(int* array) { return 0; }
Hai hàm này chính là hai hàm được sử dụng trong con trỏ hàm để thực hiện chuyển
đổi số có dấu (hay không dấu)
void printString(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[ i];
if ((i + 1) % 8 == 0 && i < n - 1) cout << " "; } cout << endl; }
Hàm printString này có chức năng tương tự như hàm in của câu 1.1 4.3. Câu 2
Các phương thức trong lớp này được viết ở trong lớp luôn mà không phải khai báo
ngoài lớp và nguyên mẫu phương thức (phương thức inline) 4.3.1. Lớp Bits: Các thuộc tính 4 lOMoAR cPSD| 59994889 class Bits { private: string bitString; … }
Các thuộc tính chỉ bao gồm một lớp string tên là bitString dùng để lưu trữ chuỗi bit. 4.3.2.
Lớp Bits: Các phương thức a)
Các phương thức trong class scope private:
static bool isValid(const string &bitStr);
Phương thức này dùng để thực hiện kiểm tra chuỗi hợp lệ. Sẽ không yêu cầu
kiểm tra độ dài chuỗi có bằng 8 hay không (lựa chọn người dùng, sau này sẽ
có phép nhân hai bit để lấy độ chính xác 16 bits)
static string bitAdd1(string sourceString);
Phương thức thêm 1 bit vào cuối chuỗi, hỗ trợ tính toán phép bù 2 và đảo bit bù 2 tìm số đối.
Hai phương thức sau dùng để thực hiện dịch tría và dịch phải, dùng cho các phép tính nhân và chia:
static string shiftLeftByOne(string A, string &Q);
static string shiftRightByOne(string P, string &Q, char &Q_1);
b) Các phương thức trong class scope public: o
Các phương thức khởi tạo (constructor) Bits() : bitString("") {}
Phương thức khởi tạo mặc định: Gắn chuỗi rỗng cho bitString
Bits(string bitStr) : bitString(bitStr) { if (!isValid(bitStr)) {
throw invalid_argument("Chuoi bit khong hop le") ; } }
Phương thức khởi tạo có đối số đầu vào là chuỗi: Gọi hàm isValid để kiểm tra
hợp lệ và ném ngoại lệ ra nếu không thỏa mãn (do là ngoại lệ nên sẽ dừng
chương trình ngay tại thời điểm ném)
o Các phương thức thực hiện phép tính Bits complimentOf2();
Thực hiện bù 2 (có đảo bit) cho bitString. Kết quả trả ra là một object Bits
có giá trị bitString được đảo theo kiểu bù 2. Bits add(Bits bits2Add) ; 5 lOMoAR cPSD| 59994889
Thực hiện cộng hai Bits và trả về Bits chứa kết quả. Sử dụng phương pháp
cộng bit như cộng hai số thập phân (có nhớ) Bits sub(Bits bit2Sub);
Theo lí thuyết là chỉ cần đảo bit lại bit2Sub sau đó cộng vào là được. Phương
thức trừ này áp dụng lí thuyết trên
Bits boothMultiply(Bits bits2Multiply) ;
Phương thức này thực hiện nhân hai Bits với nhau dựa trên Thuật toán nhân cải tiến của Booth
pair restoreDivision(Bits bit2Divide);
Phương thức này trả về một cặp dữ liệu Bits cho số thương và số dư (được trả về dạng bù 2)
o Các phương thức hủy (destructor)
Do trong các thuộc tính và phương thức hầu như không có con trỏ (kể cả con
trỏ hàm) hay các khối bộ nhớ động (mảng động) được tạo nên destructor sẽ
được để mặc định theo destructor của trình biên dịch, các bộ nhớ sau khi
dùng xong được hủy theo cơ chế STACK. o Các phương thức khác void display() const {
for (int i = 0; i < bitString.length(); i++){ cout << bitString[i];
if ((i + 1) % 8 ==0 ) cout << " "; } cout << endl; }
Phương thức hiển thị chuỗi ra màn hình. Thể hiện tương tự như các hàm in ở câu 1.1 và 1.2
5.Kết quả thực hiện các yêu cầu 5.1. Câu 1 Test case như sau: Câu
Đầu vào – Kết quả mong đợi
- 10 - 11110110 (trước đó là 24 bit 1)
15 – 00001111 (trước đó là 24 bit 0) 0 – 32 bit 0 1 1.1 -1 – 32 bit 1
2147483647 – 1 bit 0 và 32 bit 1 theo sau
-2148473648 – 1 bit 1 và 32 bit 0 theo sau 6 lOMoAR cPSD| 59994889 signedInteger:
11111111 11111111 11110001 11000001 - -3647
11111111 11111111 11111111 11111111 - -1 1.2 unsignedInteger:
00000000 00000000 00001010 00011001 – 2585
11111111 11111111 11111111 11111111 - 4294967295
Màn hình kết quả (console) 5.2. Câu 2 Test case như sau: Test case Kết quả mong đợi 00001111 + 01000100 (15 + 68) 01010011(83)
00010111 – 10110101 (23 – (-75)) 01100010 (98)
00100010 * 10111101 (34 * -67) 11110111 00011010 (-2278)
00001110 / 11111101 (14 / (-3)) Thương: 11111100 (-4) Dư: (00000010) (2)
Màn hình kết quả (console) 6.Một số lưu ý
- Các chương trình sẽ có hai hàm main: o
Một hàm main chứa menu chạy
chương trình để nhập dữ liệu tùy ý o Một 7 lOMoAR cPSD| 59994889
menu chứa các test case đã thực hiện,
được bỏ trong cặp dấu comment /* */
Có thể thực hiện sử dụng một trong hai hàm main của chương trình nếu muốn, tuy
nhiên không được bỏ cả hai hàm main vào vì sẽ gây ra lỗi biên dịch.
- Các thư viện được sử dụng: o - Nhập xuất cơ bản o - Ném ngoại lệ o
- Hỗ trợ cho đối tượng string o
- Hỗ trợ đầy đủ cho pair
- Trong source code bài 2 có đi kèm theo một hàm restoreDivision khác trong dấu
comment /* */: static Bits restoreDivision(Bits dividend Bits divisor);
Hàm này thực hiện chức năng tương tự tuy nhiên chỉ trả ra giá trị của phần thương,
không trả ra giá trị phần dư
- Theo định nghĩa của phép chia nguyên thì ta sẽ thực hiện theo bài làm, còn theo
định nghĩa chính xác thì ta sẽ phải lấy số nguyên gần nhất có thể chia hết cho số
chia sau đó thực hiện chia và từ đó tính được dư. Trong trường hợp này, phép chia
theo thuật toán trên sẽ sai
- Theo thuật toán chia, có thể thấy được nhược điểm của thuật toán này là sẽ chỉ cho
ra kết quả chính xác khi cả hai đầu vào (số bị chia, số chia) là số nguyên dương.
(Theo như ví dụ trong Giáo trình). Do đó, một “thủ thuật” nho nhỏ được áp dụng đó
chính là: lấy phần chia nguyên dương, sau đó gán dấu vào tùy theo dấu của số bị chia, số chia 7.Kết luận
Trong khi thực hiện bài tập này, sẽ có vài sự cố không mong muốn, đôi khi xuất hiện trong
lúc thực thi, dẫn đến các kết quả trả ra không theo mong muốn. Điều này là do trình độ còn
“non” của em trong việc lập trình, mong được thầy “nương tay” ạ. Em cảm ơn thầy rất nhiều. 8