STDIO
Tìm kiếm gần đây

    Nội dung

    Phép Cộng Trừ Hai Số Lớn

    Phi Phạm

    10/04/2015
    07/04/2017
    Phép Cộng Trừ Hai Số Lớn
    Trong các ngôn ngữ lập trình, kiểu số của chúng ta thường bị giới hạn ở một mức nào đó. Tuy nhiên có những lúc ta cần phải thao tác với những số vượt quá giới hạn này. Bài viết sẽ hướng dẫn cách hiện thực phép cộng và trừ với số lớn dựa vào các kiểu dữ liệu và hàm sẵn có.

    Giới thiệu

    Trong các ngôn ngữ lập trình, kiểu số của chúng ta thường bị giới hạn ở một mức nào đó. Ví dụ như kiểu dữ liệu int của ngôn ngữ C++ thường giới hạn ở mức–2,147,483,648 đến 2,147,483,647. Tuy nhiên có những lúc ta cần phải thao tác với những số vượt quá giới hạn này. Do đó ta cần phải có những phương pháp khác nhau để giải quyết vấn đề này.

    Bài viết giới thiệu đến bạn đọc một giải pháp hiện thực phép cộng trừ dành cho các số lớn.

    Phép cộng hai số lớn

    Lựa chọn kiểu dữ liệu

    Ví dụ: với một số nguyên lớn có 20 chữ số, một biến thông thường không thể nào thể hiện được  toàn bộ số lớn này. Vì vậy chúng ta chọn cách dùng nhiều biến để biểu diễn từng chữ số, như vậy ta có một mảng các chữ số để biểu diễn cho một số lớn. Một chữ số có giá trị từ 0 – 9 nên để tối ưu và đơn giản cho thao tác nhập mảng, ta sẽ sử dụng mảng kiểu char.

    Vậy, prototype của hàm cộng hai số lớn sẽ là:

    char* addBigNumber(char* a, char* b);

    Với hai chuỗi a, b là hai số lớn cần tính toán.

    Hiện thực phép toán

    Khi cộng hai số a và b, ta có hai trường hợp sau :

    • Số a có chiều dài (số chữ số) lớn hơn hoặc bằng số b.
    • Số b có chiều dài lớn hơn hoặc bằng số a.

    Vậy để tổng quát hóa hai trường hợp trên, ta sẽ so sánh chiều dài hai số a và b, nếu số b có chiều dài lớn hơn số a, ta thực hiện đảo giá trị hai pointer chứa địa chỉ mảng a và mảng b. Từ đó, ta có số a luôn luôn có chiều dài lớn hơn hoặc bằng số b. Để đơn giản cho thao tác tìm độ dài chuỗi, ta sử dụng hàm strlen() trong thư viện string.h. Tìm hiểu thêm về thư viện string.h qua bài viết Thao tác với chuỗi trong C/C++.

    if (strlen(a) < strlen(b))
    {
    	swapPointer(&a, &b);
    }
    

    Hàm swapPointer được định nghĩa như sau:

    void swapPointer(char** a, char** b)
    {
    	char* temp = *a;
    	*a = *b;
    	*b = temp;
    }

    Ta khai báo một số biến cần thiết trong quá trình tính toán như sau:

    • a_len, b_len là chiều dài hai số a, b.
    • result là kết quả a + b. chiều dài của result luôn bằng hoặc lớn hơn chiều dài số a một đơn vị tùy trường hợp nên ta cấp phát cho result thêm một byte, một byte nữa là dành cho ký tự rỗng cuối chuỗi.
    • remember là biến chỉ trạng thái “nhớ” của phép tính khi cộng 2 chữ số, ban đầu là  false.
    size_t a_len = strlen(a), b_len = strlen(b);
    char* result = new char[a_len + 2];
    bool remember = false;

    Khi thực hiện cộng 2 số, ta lại có hai công đoạn:

    • Tính tổng các chữ số của cả a và b (phần bên phải).
    • Tính tổng các chữ số của a với 0 (phần bên trái).

    ss_1

    Như vậy chúng ta cần hai vòng lặp để làm những việc này.

    Bước 1

    Ta có thể dễ dàng thấy, số lần lặp của công đoạn này sẽ là b_len, số chữ số của b. vậy ta có vòng lặp như sau: 

    for (int i = 0; i < b_len; i++)
    {
    	//...
    }
    

    Ta cần tính tổng các chữ số từ phải qua trái, vậy ta lấy giá trị các chữ số này bằng cách sử dụng  a[a_len - i - 1] và b[b_len - i - 1]. Mỗi giá trị hiện tại đang được lưu trong mảng với kiểu char, vậy để lấy được chính xác giá trị kiểu số của các chữ số này, ta trừ mỗi giá trị cho 48 (hay ký tự ‘0’). Ví dụ: ký tự ‘9’ trong kiểu char có giá trị là 57, vậy để lấy được số 9, ta lấy 57 trừ đi 48 hay ký tự ‘0’ (có giá trị là 48) được 9.

    Ta dùng một biến tạm để lưu tổng của 2 giá trị này:

    int temp = *(b + b_len - i - 1) - '0' + *(a + a_len - i - 1) - '0';

    Ta có ví dụ: khi cộng 18 với 13, lấy 8 + 3 = 11, kết quả >= 10 nên chỉ lấy chữ số hàng đơn vị là 1, nhớ 1, tiếp theo, ta lấy 1 + 1 được 2, vì có nhớ nên ghi 3. Kết quả là 31. Theo logic đó, tiếp theo ta xét giá trị biến remember, nếu là true ta cộng temp lên 1 đơn vị, nếu temp có giá trị >= 10, ta set remember  = true, ngược lại ta set remember = false. Để lấy chữ số hàng đơn vị của temp, ta lấy temp chia phần dư cho 10.

    if (remember)
    	temp++;
    
    if (temp > 9)
    	remember = true;
    else
    	remember = false;
    
    temp = temp % 10;

    Vậy là ta đã tính được tổng các chữ số của a và b, việc còn lại là gán giá trị này vào mảng result. Tương tự cách làm ở trên, để ghi được ký tự ‘9’ vào mảng, ta cộng số 9 với 48 hay ‘0’.

    *(result + a_len - i) = temp + '0';

    Vậy ta có code hoàn chỉnh cho vòng lặp vừa rồi như sau:

    for (int i = 0; i < b_len; i++)
    {
    	int temp = *(b + b_len - i - 1) - '0' + *(a + a_len - i - 1) - '0';
    
    	if (remember)
    		temp++;
    
    	if (temp > 9)
    		remember = true;
    	else
    		remember = false;
    
    	temp = temp % 10;
    
    	*(result + a_len - i) = temp + '0';
    }

    Với vòng lặp này, chúng ta đã có thể cộng hai số lớn có chiều dài bằng nhau.

    Bước 2

    Tương tự các bước của công đoạn thứ nhất, số lần lặp của công đoạn này là: a_len - b_len.

    Giai đoạn này chỉ cần lấy giá trị các chữ số của a bằng cách sử dụng:  a[a_len – b_len – i - 1], từ đó có giá trị biến temp là: 

    int temp = a[a_len - b_len - i – 1] - '0';

    Tương tự ta có giá trị result như sau:

    result[a_len - b_len – i] = temp + '0';

    Ta có code hoàn chỉnh:

    for (int i = 0; i < a_len - b_len; i++)
    {
    	int temp = *(a + a_len - b_len - i - 1) - '0';
    
    	if (remember)
    		temp++;
    	if (temp > 9)
    		remember = true;
    	else
    		remember = false;
    
    	temp = temp % 10;
    
    	*(result + a_len - b_len - i) = temp + '0';
    }

    Để đánh dấu kết thúc chuỗi result, ta gán:

    result[a_len + 1] = '\0';

    Lấy ví dụ 1 + 9999, làm lần lượt các bước như trên, chúng ta được result có 4 chữ số, nhưng rõ ràng ở đây, đáp án là 10000 có 5 chữ số. Để làm được việc này, ta xét giá trị biến remember, nếu là true: set giá trị result[0] = ‘1’, ngược lại, dịch tất cả các phần tử của mảng result sang bên trái một đơn vị.

    if (remember)
    {
    	*(result) = '1';
    }
    else
    {
    	for (int i = 0; i <= a_len; i++)
    		*(result + i) = *(result + i + 1);
    }

    Cuối cùng, ta trả về result – kết quả của a + b.

    Test thử với hàm main:

    int main()
    {
    	char* a = "12345678987654321", *b = "98765432123456789";
    	char* c = addBigNumber(a, b);
    	printf("%s", c);
    	delete[] c;
    }

    Ta được output:  111111111111111110 là chính xác.

    Code hoàn chỉnh của bài này:

    char* addBigNumber(char* a, char* b)
    {
    	if (strlen(a) < strlen(b))
    	{
    		swapPointer(&a, &b);
    	}
    
    	size_t a_len = strlen(a), b_len = strlen(b);
    	char* result = new char[a_len + 2];
    	memset(result, '0', a_len);
    	bool remember = false;
    
    	for (int i = 0; i < b_len; i++)
    	{
    		int temp = *(b + b_len - i - 1) - '0' + *(a + a_len - i - 1) - '0';
    
    		if (remember)
    			temp++;
    
    		if (temp > 9)
    			remember = true;
    		else
    			remember = false;
    
    		temp = temp % 10;
    
    		*(result + a_len - i) = temp + '0';
    	}
    
    	for (int i = 0; i < a_len - b_len; i++)
    	{
    		int temp = *(a + a_len - b_len - i - 1) - '0';
    
    		if (remember)
    			temp++;
    		if (temp > 9)
    			remember = true;
    		else
    			remember = false;
    	
    		temp = temp % 10;
    
    		*(result + a_len - b_len - i) = temp + '0';
    	}
    
    	*(result + a_len + 1) = '\0';
    
    	if (remember)
    	{
    		*(result) = '1';
    	}
    	else
    	{
    		for (int i = 0; i <= a_len; i++)
    			*(result + i) = *(result + i + 1);
    	}
    
    	return result;
    }

    Phép trừ hai số lớn

    Tương tự phép cộng, prototype của hàm trừ hai số lớn sẽ là:

    char* subBigNumber(char* a, char* b);

    Với hai chuỗi a, b là hai số lớn cần tính toán.

    Hiện thực phép toán

    Khi trừ hai số a và b, ta phải biết số nào lớn hơn để thực hiện phép trừ. Ví dụ: khi thực hiện phép toán: 99 – 100. Ta xác định 100 lớn hơn 9 nên lấy 100 – 99 = 1, thêm dấu trừ ta được kết quả -1. Vì vậy, để cho thuận tiện, ta kiểm tra số b có lớn hơn a hay không, nếu có thì ta đảo hai pointer chứa địa chỉ hai mảng a, b và thêm dấu trừ vào trước kết quả.

    bool sign = false, remember = false;
    
    if (strlen(a) < strlen(b))
    {
    	sign = true;
    	swapPointer(&a, &b);
    }
    else if (strlen(a) == strlen(b))
    {
    	for (int i = strlen(a) - 1; i >= 0; i--)
    	{
    		if (*(a + i) < *(b + i))
    		{
    			swapPointer(&a, &b);
    			sign = true;
    		}
    	}
    }

    Đoạn code trên sẽ kiểm tra độ dài 2 số, nếu bằng nhau sẽ tiếp tục so sánh từng chữ số từ phải qua trái để tìm ra số lớn hơn, sau đó đảo vị trí các pointer (nếu cần).

    Ta khai báo và gán giá trị một số biến cần thiết trong quá trình tính toán như sau:

    size_t a_len = strlen(a), b_len = strlen(b);
    char* result = new char [a_len + 2];
    memset(result, '0', a_len + 2);

    result được cấp phát thêm 2 bytes: một byte dành cho ký tự rỗng cuối chuỗi, một byte cho dấu trừ đầu chuỗi nếu kết quả là số âm.

    Tương tự phép cộng, khi thực hiện trừ hai số, ta lại có hai công đoạn:

    • Tính hiệu các chữ số của a cho b (phần bên phải).
    • Tính hiệu các chữ số của a với 0 (phần bên trái).

    ss_2

    Như vậy chúng ta cũng cần hai vòng lặp để làm những việc này.

    Bước 1

    Số lần lặp của công đoạn này sẽ là b_len, số chữ số của b. vậy ta có vòng lặp như sau:

    for (int i = 0; i < b_len; i++)
    {
    	//...
    }

    Ta cần tính hiệu các chữ số từ phải qua trái, vì phép trừ nên chỉ cần số chênh lệch giữa 2 số nên ta có:

    int temp = *(a + a_len - i - 1) - *(b + b_len – i - 1);

    Theo như logic của phép trừ, khi một chữ số của a nhỏ hơn b, thì khi trừ phải mượn 1 từ chữ số tiếp theo bên trái. Và kết quả phép trừ được cộng thêm 10, kết quả phép trừ tiếp theo sẽ giảm 1 đơn vị do mượn 1 từ phép trừ vừa rồi. Vậy ta có đoạn code như sau: 

    if (remember == true)
    	temp--;
    if (temp < 0)
    {
    	temp += 10;
    	remember = true;
    }
    else
    	remember = false;

    Việc tiếp theo chỉ là gán kết quả vừa tính vào result:

    *(result + a_len – i) = temp + '0';

    Vậy ta có code hoàn chỉnh cho vòng lặp vừa rồi như sau:

    for (int i = 0; i < b_len; i++)
    {
    	int temp = *(a + a_len – i - 1) - *(b + b_len – i - 1);
    
    	if (remember == true)
    		temp--;
    	if (temp < 0)
    	{
    		temp += 10;
    		remember = true;
    	}
    	else
    		remember = false;
    
    	*(result + a_len - i) = temp + '0';
    }

    Bước 2

    Tương tự các bước của công đoạn thứ nhất, số lần lặp của công đoạn này là: a_len - b_len.

    Giai đoạn này chỉ cần lấy giá trị các chữ số của a bằng cách sử dụng:  a[a_len – b_len – i], từ đó có giá trị biến temp là:

    int temp = a[a_len - b_len - i] - '0';

    tương tự ta có giá trị result như sau:

    result[a_len - b_len – i + 1] = temp + '0';

    vậy ta có code hoàn chỉnh: 

    for (int i = 0; i < a_len - b_len; i++)
    {
    	int temp = *(a + a_len - b_len – i - 1) - '0';
    
    	if (remember == true)
    		temp--;
    	if (temp < 0)
    	{
    		temp += 10;
    		remember = true;
    	}
    	else
    		remember = false;
    
    	*(result + a_len - b_len - i) = temp + '0';
    }

    Ví dụ: 1000 – 999 với những gì đã làm ta được kết quả là 0001, vậy vấn đề còn lại là  xóa số 0 trước chuỗi và thêm dấu trừ (nếu có) vào đầu chuỗi dựa vào giá trị biến sign. 

    while (*(result) == '0')
    {
    	if (*(result + 1) != '0' && sign == true)
    	{
    		*(result) = '-';
    		*(result + a_len + 1) = '\0';
    		break;
    	}
    
    	for (int i = 0; i < a_len; i++)
    	{
    		*(result + i) = *(result + i + 1);
    	}
    	*(result + a_len) = '\0';
    }

    Cuối cùng, ta trả về result – kết quả của a - b.

    Test thử với hàm main:

    int main()
    {
    	char* a = "12345678987654321", *b = "98765432123456789";
    	char* c = addBigNumber(a, b);
    	printf("%s", c);
    	delete[] c;
    }

    Ta được output: -6419753135802468  là chính xác.

    Code hoàn chỉnh của bài này :

    char* subBigNumber(char* a, char* b)
    {
    	bool sign = false, remember = false;
    
    	if (strlen(a) < strlen(b))
    	{
    		sign = true;
    		swapPointer(&a, &b);
    	}
    	else if (strlen(a) == strlen(b))
    	{
    		for (int i = strlen(a) - 1; i >= 0; i--)
    		{
    			if (*(a + i) < *(b + i))
    			{
    				swapPointer(&a, &b);
    				sign = true;
    			}
    		}
    	}
    	size_t a_len = strlen(a);
    	size_t b_len = strlen(b);
    	char* result = new char [a_len + 2];
    	memset(result, '0', a_len + 2);
    
    	for (int i = 0; i < b_len; i++)
    	{
    		int temp = *(a + a_len - i - 1) - *(b + b_len - i - 1);
    
    		if (remember)
    			temp--;
    		if (temp < 0)
    		{
    			temp += 10;
    			remember = true;
    		}
    		else
    			remember = false;
    
    		*(result + a_len - i) = temp + '0';
    	}
    
    	for (int i = 0; i < a_len - b_len; i++)
    	{
    		int temp = *(a + a_len - b_len - i - 1) - '0';
    
    		if (remember == true)
    			temp--;
    		if (temp < 0)
    		{
    			temp += 10;
    			remember = true;
    		}
    		else
    			remember = false;
    
    		*(result + a_len - b_len - i) = temp + '0';	
    	}
    
    	while (*(result) == '0')
    	{
    		if (*(result + 1) != '0' && sign == true)
    		{
    			*(result) = '-';
    			*(result + a_len + 1) = '\0';
    			break;
    		}
    
    		for (int i = 0; i < a_len; i++)
    		{
    			*(result + i) = *(result + i + 1);
    		}
    		*(result + a_len) = '\0';
    	}
    
    	return result;
    }

    Lời kết

    Qua bài viết này, hy vọng bạn đọc đã tìm được cho mình giải pháp để giải quyết việc tính toán trên số lớn. Và với tư tưởng như trên,bạn đọc hoàn toàn có thể phát triển thêm các phép toán khác như: nhân, chia, lấy phần dư ...

     

    Thảo luận

    In order to comment you must be a STDIO Insider. Please sign up or log in to continue.

    Đăng nhập

    Bài viết liên quan

    Vector Và Ứng Dụng Của Chúng

    Vector Và Ứng Dụng Của Chúng

    Vector là một khái niệm rất quen trong toán học; và chúng được ứng dụng trong rất nhiều lĩnh vực khác nhau: đồ họa máy tính, mô phỏng vật lý … Bài viết này muốn giới ...

    Vũ Quang Huy

    26/09/2014

    BigData - Xu Thế Hay Điều Tất Yếu Đang Xảy Ra

    BigData - Xu Thế Hay Điều Tất Yếu Đang Xảy Ra

    BigData là một khái niệm, để miêu tả về một khối lượng dữ liệu lớn, khổng lồ. Lớn đến mức dữ liệu không thể lưu trữ trong các hệ thống cơ sở dữ liệu quan hệ truyền thống. ...

    Lê Minh Trung

    26/05/2015

    Xử Lý Ảnh Với OpenCV: Lọc Số Trong Ảnh

    Xử Lý Ảnh Với OpenCV: Lọc Số Trong Ảnh

    Nẳm trong loạt bài viết trong chương trình Tự Học OpenCV Qua Các Ví Dụ Thực Tế. Bài viết sẽ giới thiệu khái niệm lọc số ảnh là gì?, khái niệm và công thức nhân chập ma ...

    Trương Xuân Đạt

    23/01/2015

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    Nẳm trong loạt bài viết trong chương trình Tự Học OpenCV Qua Các Ví Dụ Thực Tế. Bài viết giới thiệu những thuật toán cơ sở trong xử lý hình thái học, và đã giới thiệu ...

    Trương Xuân Đạt

    23/01/2015

    C# Script - Lớp Quaternion

    C# Script - Lớp Quaternion

    Quaternion là một thuật ngữ có lẽ khá xa lạ đối với nhiều lập trình viên. Thuật ngữ này được khởi nguồn từ lý thuyết toán học, được ứng dụng trong các phép quay không ...

    Rye Nguyen

    08/08/2015

    Làm Việc Nhóm Với Team Foundation Server (TFS)

    Làm Việc Nhóm Với Team Foundation Server (TFS)

    Bài viết hướng về chia sẻ kinh nghiệm khi sử dụng Visual Studio trong việc lập trình, cụ thể là chia sẻ về cách tạo một Team Foundation Server - TFS. ...

    Tuấn Trần

    18/08/2015

    Toán Tử Trong PHP

    Toán Tử Trong PHP

    Trong tất cả các ngôn ngữ lập trình, muốn thực hiện thao tác tính toán thì luôn cần phải có toán tử. PHP cũng là một ngôn ngữ lập trình như vậy, có toán tử để thực hiện ...

    Phạm Hoài Nguyên

    03/10/2016

    Giới Thiệu Thị Trường Tiền Điện Tử Và Công Nghệ Lưu Trữ

    Giới Thiệu Thị Trường Tiền Điện Tử Và Công Nghệ Lưu Trữ

    Trình bày tổng quát về đồng tiền điện tử, mô hình giao dịch, công nghệ và cách thứ lưu trữ đồng tiền điện tử để mang lại cho bạn đọc thêm kiến thức, cái nhìn khách quan ...

    Nguyễn Hồng Sơn

    13/03/2016

    Hiện Thực Quadtree Và Ứng Dụng Trong Lập Trình Game

    Hiện Thực Quadtree Và Ứng Dụng Trong Lập Trình Game

    Xét va chạm (Collision Detection) là một việc quan trọng trong lập trình game. Công việc này đòi hỏi chi phí cao, đặc biệt khi số lượng thực thể (entity) trong game là ...

    Rye Nguyen

    31/07/2015

    Tính Hiệu Quả Và Khả Thi Trong Việc Sử Dụng Hệ Thống Chơi Game Thực Tại Ảo Tại Gia Cho Người Lớn Tuổi

    Tính Hiệu Quả Và Khả Thi Trong Việc Sử Dụng Hệ Thống Chơi Game Thực Tại Ảo Tại Gia Cho Người Lớn Tuổi

    Hệ thống chơi game thực tại ảo có thể sử dụng cho người lớn tuổi tại gia, từ đó tạo điều kiện cho các hoạt động thể chất để cải thiện các khiếm khuyết, các hoạt động bị ...

    Kanzaki Nguyen

    14/08/2015

    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    developer@stdio.vn

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020