Số nguyên và tràn số — two's complement và khi phép cộng ra số âm

TL;DR: Máy lưu số âm bằng two's complement — đảo toàn bộ bit rồi cộng 1. Cách này giúp phép cộng và trừ dùng chung một mạch, và không có hai biểu diễn của số 0. Khi cộng hai số int vượt 2.147.483.647, kết quả wrap-around về âm chứ không báo lỗi — đây là tràn số (overflow). Python int vô hạn nên không tràn; Java/C/Go có kích thước cố định nên tràn âm thầm. Chọn int khi miền giá trị chắc chắn trong 32-bit, long khi đếm mili-giây, tiền, hay bất kỳ thứ gì có thể vượt 2 tỷ.

Năm 2012, video "Gangnam Style" của PSY phá mọi kỷ lục YouTube. Kỹ sư Google thở phào — bộ đếm view dùng kiểu int 32-bit, tối đa khoảng 2,147,483,647 lượt. Đến tháng 12/2014, con số ấy không đủ nữa. Nếu bộ đếm tràn, nó sẽ nhảy sang âm — hàng tỷ lượt xem hiển thị thành số âm trên giao diện. Google phải vá khẩn cấp, chuyển sang int64. Đây không phải tai nạn — đây là hành vi được định nghĩa rõ của kiểu số nguyên kích thước cố định.

Bài này giải thích vì sao tràn số xảy ra, cơ chế two's complement cho phép máy biểu diễn số âm, và cách chọn kiểu để tránh bug ấy trong code thật.

1. Analogy — đồng hồ đo kilômét quay vòng

Xe máy cũ có đồng hồ cơ 6 chữ số: 000000 đến 999999. Chạy thêm 1 km sau 999999 không báo lỗi — nó quay về 000000. Tương tự, cộng thêm vào 999999 thì ta ra 000001 — ngỡ như chạy ít hơn, thực ra đã quay vòng.

Số nguyên trong máy tính hoạt động theo cùng nguyên lý, chỉ là "đồng hồ" đếm theo nhị phân và có điểm gập ở giữa (để chứa cả âm lẫn dương).

2. Số nguyên không dấu và có dấu

2.1 Không dấu (unsigned): toàn bộ dải là dương

Với n bit, unsigned biểu diễn dải 0 đến 2^n − 1. Mọi tổ hợp bit đều là số không âm.

Ví dụ thực tế: địa chỉ IPv4 (4 byte, mỗi byte 0–255), ảnh PNG lưu màu pixel.

2.2 Có dấu (signed): two's complement

Hầu hết ngôn ngữ dùng two's complement để biểu diễn số âm. Ý tưởng: cắt dải n-bit thành đôi, nửa trên là số âm.

Quy tắc lấy số âm từ số dương:

1. Viết số dương dưới dạng nhị phân n bit.
2. Đảo toàn bộ bit (0 thành 1, 1 thành 0) — gọi là bitwise NOT.
3. Cộng thêm 1.

Ví dụ với 8 bit, tìm biểu diễn của -3:

+3  =  0000 0011
NOT =  1111 1100
+1  =  1111 1101   <- day la -3 trong two's complement

Kiểm tra ngược: lấy 1111 1101, đảo bit ra 0000 0010, cộng 1 ra 0000 0011 = 3. Đúng.

Vì sao chọn two's complement, không phải cách khác?

Cách ngây thơ nhất là dùng 1 bit cao nhất làm "dấu" (sign-magnitude): 0 = dương, 1 = âm. Cách này có hai vấn đề nghiêm trọng: (1) tồn tại hai biểu diễn của số 0 (0000 0000 và 1000 0000), gây logic phức tạp khi so sánh; (2) phép cộng và phép trừ cần mạch riêng, làm chip tốn kém hơn.

Two's complement giải quyết cả hai: chỉ có một biểu diễn của số 0, và phép cộng số âm với số dương dùng chung mạch cộng với số unsigned — CPU không cần phân biệt dấu khi thực hiện phép tính.

  1111 1101   (-3 trong two's complement)
+ 0000 0011   (+3)
-----------
1 0000 0000   -> bit carry tran ra ngoai 8 bit, phan con lai = 0 ✓

Dải giá trị có dấu 32-bit:

• Tối thiểu: −2^31 = −2.147.483.648 (thường gọi INT_MIN)
• Tối đa: 2^31 − 1 = 2.147.483.647 (thường gọi INT_MAX)

Lý do tối thiểu có trị tuyệt đối lớn hơn tối đa 1 đơn vị: bit pattern 1000...0 (bit cao nhất là 1, còn lại là 0) là INT_MIN, và không có +INT_MIN tương ứng trong dải 32-bit.

flowchart LR
  A["0 den 2^31-1\n(bit cao nhat = 0)"] -->|"wrap-around"| B["−2^31 den −1\n(bit cao nhat = 1)"]
  B -->|"wrap-around"| A

3. Tràn số — wrap-around modular

Khi cộng hai số có dấu mà kết quả vượt INT_MAX, bit carry tràn ra ngoài và phần còn lại là một số âm. Đây là signed overflow.

// Java: int la 32-bit signed
int a = 2_000_000_000;   // 2 ty
int b = 2_000_000_000;   // 2 ty
int c = a + b;           // mong 4 ty, nhung 4 ty > INT_MAX
System.out.println(c);   // -294967296 (so am, sai hoan toan)

# Python: int la bignum, khong tran
a = 2_000_000_000
b = 2_000_000_000
c = a + b
print(c)  # 4000000000, dung

// Go: int32 tran, int64 khong tran
var a int32 = 2_000_000_000
var b int32 = 2_000_000_000
fmt.Println(a + b)  // -294967296

var x int64 = 2_000_000_000
var y int64 = 2_000_000_000
fmt.Println(x + y)  // 4000000000

Khác biệt quan trọng giữa ngôn ngữ:

C/C++ undefined behavior khi tràn signed là điều đặc biệt nguy hiểm: compiler được phép giả sử tràn không xảy ra và tối ưu hoá dựa trên giả sử đó, khiến code hoạt động sai theo những cách không thể đoán trước. Đây là nguồn gốc của nhiều lỗ hổng bảo mật nghiêm trọng.

4. Áp dụng vào code của bạn

4.1 Chọn int hay long

Nguyên tắc: chọn kiểu nhỏ nhất chứa đủ miền giá trị tối đa có thể xảy ra.

4.2 Sửa bug binary search — sai rồi đúng

// SAI: (low + high) tran neu ca hai lon
int mid = (low + high) / 2;

// DUNG: (high - low) luon nho, khong tran
int mid = low + (high - low) / 2;

// CACH KHAC (Java): dung unsigned shift right
int mid = (low + high) >>> 1;

Cách >>> 1 (unsigned right shift) hoạt động vì kể cả khi low + high tràn sang bit dấu, dịch phải không dấu vẫn cho kết quả số học đúng cho giá trị dương lớn.

4.3 Phát hiện và phòng tránh tràn số

Java — dùng Math.addExact:

// Math.addExact nem ArithmeticException khi tran thay vi wrap
try {
    long result = Math.addExact(a, b);
} catch (ArithmeticException e) {
    // xu ly truong hop tran so
}

Kiểm tra trước khi cộng (ngôn ngữ không có addExact):

// C: kiem tra truoc khi cong
if (a > 0 && b > INT_MAX - a) {
    // tran duong
}
if (a < 0 && b < INT_MIN - a) {
    // tran am
}

Dùng kiểu rộng hơn:

// Ep sang long truoc khi nhan/cong, tra ve int sau khi kiem tra
long product = (long) a * b;   // ep truoc khi nhan
if (product > Integer.MAX_VALUE) {
    throw new ArithmeticException("overflow");
}
return (int) product;

5. Liên hệ các bài khác

• Bài 01 — Bit, byte và hệ cơ số: nền tảng cần thiết — công thức 2^n giải thích tại sao INT_MAX = 2^31 − 1.
• Bài 03 — Số thực IEEE 754: số thực cũng có tràn (infinity) và mất độ chính xác — bài sau; cơ chế khác nhưng cùng gốc rễ "n bit hữu hạn".
• Bài thao tác bit (module sau): two's complement liên quan trực tiếp tới các phép dịch bit và bitmask — hiểu now giúp bài đó dễ hơn nhiều.

6. Tóm tắt

• Unsigned n bit: dải 0 đến 2^n − 1. Signed n bit (two's complement): −2^(n−1) đến 2^(n−1) − 1.
• int 32-bit: INT_MIN = −2.147.483.648, INT_MAX = 2.147.483.647.
• Two's complement — lấy số âm bằng đảo bit rồi cộng 1. Ưu điểm: một biểu diễn duy nhất của 0, phép cộng dùng chung mạch với unsigned.
• Tràn số (overflow) không báo lỗi — kết quả wrap-around sang âm (Java, Go) hoặc undefined behavior (C/C++).
• Python int là bignum, không giới hạn kích thước, không tràn.
• Bug binary search (low + high) / 2 tràn khi cả hai lớn — fix bằng low + (high - low) / 2.
• Chọn long khi giá trị có thể vượt 2 tỷ: timestamp mili-giây, tiền, đếm view, ID lớn.

7. Tự kiểm tra

Bài tiếp theo: Số thực IEEE 754