Trong bài viết này, chúng ta sẽ tìm hiểu cách giải quyết bài toán cộng hai số lớn trong Python.
Đề bài
Cho hai số lớn, yêu cầu cộng chúng và hiển thị kết quả.
Cách tiếp cận đơn giản là sử dụng toán tử + giữa hai toán hạng hoặc lưu hai số trong một iterable và dùng hàm sum() có sẵn trong thư viện chuẩn. Tuy nhiên, cách này làm tăng độ phức tạp thời gian vì tính toán trực tiếp trên số thập phân.
Cách khác là thao tác trực tiếp trên các bit của số thập phân, sử dụng khái niệm bộ cộng toàn phần (full adder) để tính tổng và nhớ.
Ví dụ triển khai
def Add(x, y):
# Lặp cho đến khi không còn nhớ (carry)
while (y != 0):
# Carry chứa các bit chung
carry = x & y
# Tổng các bit của x và y (XOR)
x = x ^ y
# Dịch carry sang trái 1 bit
y = carry << 1
return x
print(Add(19, 34))
Kết quả
53
Tất cả biến và hàm được khai báo ở phạm vi toàn cục.
Kết luận
Bài viết đã trình bày cách cộng hai số nhờ bộ cộng toàn phần (full adder) bằng thao tác bitwise.