Cộng nhị phân và bộ cộng nửa

Số nhị phân chỉ dùng chữ số 0 và 1. Cộng từ **phải sang trái**: `0+0=0`, `0+1=1`, `1+0=1`, còn `1+1=10₂` (viết 0 ở cột đang cộng và **nhớ 1** sang cột bên trái). Nếu một cột có thêm bit nhớ, cộng cả bit đó. Ví dụ `1010₂ + 101₂`: viết `101₂` thành `0101₂` để thẳng cột. Từ phải qua trái được các bit `1`, `1`, `1`, `1`; kết quả `1111₂`. Kiểm lại theo hệ mười: `1010₂=10`, `101₂=5`, tổng bằng 15, đúng với `1111₂`.

Khi chỉ cộng **hai bit** `x`, `y` và **chưa có bit nhớ đi vào**, có bốn trường hợp: | x | y | Tổng nhị phân | Bit nhớ z | Bit kết quả t | |---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 0 | 1 | | 1 | 1 | 10₂ | 1 | 0 | So với bảng chân trị, **bit nhớ `z = x AND y`**, còn **bit kết quả `t = x XOR y`**. Đó là ý tưởng của **bộ cộng nửa**. Nếu đã có bit nhớ từ cột bên phải đi vào, cần xử lí thêm đầu vào ấy; không dùng riêng bảng hai đầu vào này cho cả phép cộng nhiều cột. Thử `1001₂ + 1011₂`: cột phải `1+1` viết 0 nhớ 1; cột tiếp `0+1+1` viết 0 nhớ 1; cột tiếp `0+0+1` viết 1; cột trái `1+1` viết 0 nhớ 1 ra ngoài. Kết quả là **`10100₂`** (9+11=20).