Hệ bù 2 (2's Complement) phổ biến trong kiến trúc máy tính.
N-bit 2's Complement biểu diễn số từ -2^(n-1) đến 2^(n-1)-1.
4 bit: -8 đến 7. 5 bit: -16 đến 15.
Tràn (Overflow) xảy ra khi cộng hai số N-bit 2's Complement, kết quả quá lớn không vừa nhóm N-bit.
Máy tính dùng thanh ghi N-bit cố định. Kết quả cộng hai số N-bit tối đa N+1 bit. Cờ Carry lưu bit thừa. Nhưng Carry không chỉ tràn.
Phát hiện tràn
Tràn khi:
- Cộng hai số âm cho kết quả dương, hoặc
- Cộng hai số dương cho kết quả âm.
Có thể kiểm tra bit dấu (MSB) của hai toán hạng và kết quả. Thay vì so sánh 3-bit, dùng 2-bit so sánh Carry-in và Carry-out từ MSB. Xét cộng N-bit 2's Complement.
Tràn khi Carry-in != Carry-out. Biểu thức tràn từ phân tích dưới:
Hình 1: MSB cả hai là 0 (số dương). Carry-in=1 -> MSB kết quả=1 (số âm - tràn), Carry-out=0. Carry-in != Carry-out -> tràn.
Hình 2: MSB cả hai là 1 (số âm). Carry-in=0 -> MSB kết quả=0 (số dương - tràn), Carry-out=1. Carry-in != Carry-out -> tràn.
Do đó Carry-in và Carry-out tại MSB đủ phát hiện tràn.
Cổng XOR phát hiện tràn.