STDIO 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ó.
Nội dung bài viết

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
ĐÓNG