Tổng hợp quy tắc bitwise, hex, nhị phân và checksum Internet trong C

Bài này gom lại các quy tắc nền tảng cho người mới học thao tác bit trong C, đi từ toán tử bitwise, hệ hex và nhị phân, đến endianness và thuật toán checksum Internet (RFC 1071). Các phần được sắp xếp theo thứ tự nên học.

1. Bitwise: hình dung mỗi bit là một công tắc

Một biến unsigned char (8 bit) giống một dãy 8 công tắc, mỗi công tắc chỉ có bật (1) hoặc tắt (0). Bit 0 nằm bên phải nhất.

vị trí bit:  7 6 5 4 3 2 1 0
giá trị:     0 0 0 0 1 0 1 1   → 11

Sáu toán tử và cách nhớ

• & (AND): “cả hai phải bật” — kết quả 1 khi cả hai bit đều là 1.
• | (OR): “một trong hai bật là được” — kết quả 1 khi ít nhất một bit là 1.
• ^ (XOR): “khác nhau thì 1”. Hai tính chất hay dùng: x ^ x = 0 và x ^ 0 = x.
• ~ (NOT): đảo mọi bit. Với số không dấu N bit, ~x = MAX - x.
• << n: nhân với 2ⁿ (ví dụ 5 << 2 = 20).
• >> n: chia cho 2ⁿ (ví dụ 20 >> 2 = 5).

Bốn câu thần chú (với n là vị trí bit)

(1 << n) tạo ra một mặt nạ (mask) chỉ có đúng bit n bằng 1. Bạn chỉ cần chọn phép toán phù hợp để áp mặt nạ đó vào x.

Lỗi hay gặp

• Nhầm & với && (bitwise và logic).
• Quên ngoặc do độ ưu tiên: x & 1 == 0 bị hiểu là x & (1 == 0). Phải viết (x & 1) == 0.
• Dùng số có dấu để dịch bit. Nên dùng unsigned và viết 1u << 31.
• Nhầm chiều đánh số bit: bit 0 luôn là bit ngoài cùng bên phải.

Cách học hiệu quả

1. Luôn viết ra dạng nhị phân, căn thẳng cột, rồi mới tính.
2. Viết hàm in nhị phân để nhìn trực tiếp kết quả.
3. Tập trên số 8 bit cho dễ nhìn.
4. Gắn với ví dụ thực tế như cờ quyền (READ, WRITE, EXEC).

#define READ  (1 << 0)
#define WRITE (1 << 1)
#define EXEC  (1 << 2)

unsigned perm = READ | WRITE;   // cấp 2 quyền
if (perm & WRITE) { /* có quyền ghi */ }
perm &= ~WRITE;                 // thu hồi quyền ghi

2. Trọng số và hệ nhị phân

Trọng số là giá trị của một vị trí bit, tính từ phải sang trái: 1, 2, 4, 8, 16, 32, 64, 128… (gấp đôi mỗi lần sang trái, vì cơ số là 2).

Quy tắc quy ra giá trị: mỗi vị trí đóng góp bit × trọng số. Bit bằng 1 thì cộng trọng số, bit bằng 0 thì bỏ qua.

trọng số:  8   4   2   1
bit:       1   0   1   1
đóng góp:  8 + 0 + 2 + 1 = 11

Lưu ý: trọng số của vị trí là cố định. Cái bằng 0 là bit ở vị trí đó, không phải trọng số. Giống số thập phân 305: chữ số 0 ở hàng chục không đóng góp gì nhưng vẫn phải có mặt để giữ chỗ.

Nhị phân không mặc định gồm 4 chữ số. Ta thường viết đủ nhóm 4 bit chỉ để tiện đổi qua lại với hex, hoặc đủ 8/16/32 bit theo kiểu dữ liệu. Số 0 ở đầu không làm đổi giá trị (101 và 0101 đều là 5).

3. Hex, nhị phân, thập phân

Bảng chữ số hex

A=10, B=11, C=12, D=13, E=14, F=15.

Hex sang nhị phân

Mỗi chữ số hex tương ứng đúng 4 bit. Đổi từng chữ số rồi viết liền nhau.

0x2B   → 0010 1011
0x9F33 → 1001 1111 0011 0011

Nếu quên bảng, dựng lại bằng trọng số 8-4-2-1: B = 11 = 8 + 2 + 1 → 1011.

Nhị phân sang hex

1. Chia dãy bit thành nhóm 4 bắt đầu từ bên phải.
2. Nhóm ngoài cùng bên trái thiếu bit thì thêm 0 vào đầu.
3. Đổi mỗi nhóm thành một chữ số hex.

101011 → 0010 | 1011 → 0x2B

Lỗi hay gặp: chia nhóm từ bên trái, dẫn đến sai kết quả.

Hex sang thập phân

Nhân từng chữ số với giá trị hàng (lũy thừa của 16: 1, 16, 256, 4096…) rồi cộng lại.

0x153  = 1×256 + 5×16 + 3 = 339
0x9F33 = 9×4096 + 15×256 + 3×16 + 3 = 40755

Cách nhanh (Horner): đi từ trái sang phải, lấy kết quả hiện tại nhân 16 rồi cộng chữ số tiếp theo.

0x153: 1 → 1×16+5 = 21 → 21×16+3 = 339

Các mốc nên nhớ: 0xFF = 255, 0xFFFF = 65535, 0x100 = 256, 0x10000 = 65536.

4. Cộng hai số hex

Cộng từng cột từ phải sang trái, giống thập phân, nhưng đủ 16 thì nhớ 1. Ở mỗi cột gọi tổng là t (đã cộng cả số nhớ):

• t < 16: viết t (đổi về chữ cái nếu ≥ 10), nhớ 0.
• t ≥ 16: viết t - 16, nhớ 1 sang cột trái.

0x2B + 0x4F:  B+F = 26 → viết A, nhớ 1;  2+4+1 = 7   → 0x7A
0xB7 + 0x9C:  7+C = 19 → viết 3, nhớ 1;  B+9+1 = 21 → viết 5, nhớ 1 → 0x153

Căn thẳng hàng theo cột

Chỉ được cộng các chữ số cùng hàng. Số ngắn hơn phải căn theo mép phải, chỗ trống bên trái lấp bằng số 0.

  4500
+ 001C
------
  451C

Nếu căn theo mép trái (như viết chữ), bạn vô tình cộng nhầm hàng và ra kết quả sai. Thêm số 0 ở đầu không đổi giá trị (0x1C = 0x001C). Đây cũng là lý do printf("%04X") in đủ 4 chữ số hex.

5. Endianness: xử lý từng byte

Số uint16_t x = 0x1234 nằm trong bộ nhớ theo hai kiểu:

• Little-endian: 34 12 (x86, hầu hết ARM).
• Big-endian: 12 34 (thứ tự byte của mạng, network order).

Cách nguy hiểm: ép kiểu con trỏ (const uint16_t *)data rồi đọc. Kết quả phụ thuộc máy, ngoài ra có thể vướng lỗi alignment và strict aliasing (undefined behavior).

Cách an toàn: đọc từng byte rồi tự ghép bằng phép dịch bit.

uint16_t w = ((uint16_t)data[i] << 8) | data[i + 1];   // byte đầu là byte cao

Các phép <<, >>, &, | tác động lên giá trị, không phụ thuộc cách xếp byte trong bộ nhớ. Xử lý từng byte không phải là né endianness, mà là chọn rõ một quy ước (ở đây là big-endian) và viết code theo quy ước đó.

Chiều ghi cũng tương tự:

buf[6] = (cksum >> 8) & 0xFF;   // byte cao trước
buf[7] = cksum & 0xFF;          // byte thấp sau

6. Checksum Internet (RFC 1071)

Checksum Internet dùng cho IP, ICMP, TCP, UDP. Ý tưởng: bên gửi cộng các word 16-bit theo phép cộng bù 1, đảo bit kết quả và đặt vào trường checksum. Bên nhận cộng lại toàn bộ (kể cả checksum), nếu dữ liệu nguyên vẹn thì kết quả sau khi đảo bit bằng 0.

Gấp carry (end-around carry)

Carry là phần tràn ra ngoài 16 bit. Trong phép cộng bù 1, phần tràn không bị bỏ mà được cộng ngược vào phần thấp.

while (sum >> 16)
    sum = (sum & 0xFFFF) + (sum >> 16);

• sum >> 16: phần carry.
• sum & 0xFFFF: 16 bit thấp.
• Phải dùng while chứ không phải if, vì phép cộng gấp có thể sinh carry mới (0x1FFFF → 0x10000 → 0x0001).

Gấp carry tương đương lấy phần dư khi chia cho 0xFFFF (65535). Với 8 bit thì chia cho 255: 0xB7 + 0x9C = 0x153 (cộng thường), còn cộng bù 1 giữ 8 bit cho 0x53 + 0x1 = 0x54. Đây là hai phép cộng khác nhau nên 0x153 không bằng 0x54.

Toán tử ~

Với sum kiểu uint32_t, ~sum đảo cả 32 bit (~0x000060CC = 0xFFFF9F33), nên phải ép (uint16_t) hoặc mask & 0xFFFF để lấy 16 bit thấp 0x9F33. Với số 16 bit không dấu, ~x = 0xFFFF - x, do đó sum + ~sum = 0xFFFF. Bên nhận cộng cả checksum vào sẽ được 0xFFFF, đảo bit ra 0x0000.

Cài đặt chuẩn

#include <stdint.h>
#include <stddef.h>

uint16_t inet_checksum(const uint8_t *data, size_t len)
{
    uint32_t sum = 0;

    for (size_t i = 0; i + 1 < len; i += 2)
    {
        sum += ((uint32_t)data[i] << 8) | data[i + 1];   // cộng từng word 16-bit
    }

    if (len & 1) sum += (uint32_t)data[len - 1] << 8;    // byte lẻ cuối, độn 0 bên phải
    while (sum >> 16) sum = (sum & 0xFFFF) + (sum >> 16); // gấp carry
    return (uint16_t)~sum;                                // bù 1
}

Ví dụ tính tay

Dữ liệu 45 00 00 1C 1B B0 00 00 (hai byte cuối dành cho checksum, để bằng 0 khi tính):

0x4500 + 0x001C + 0x1BB0 + 0x0000 = 0x60CC
~0x60CC = 0x9F33  → checksum

Sau khi chèn: 45 00 00 1C 1B B0 9F 33. Bên nhận tính lại ra 0x0000 (hợp lệ). Nếu byte thứ 3 bị đảo (00 → FF), kết quả là 0x00FF, khác 0 nên phát hiện được lỗi.

Lỗi kinh điển: đặt sai ngoặc của vòng for

Nếu đặt { } bao luôn phần if, while và return vào thân vòng for, hàm sẽ return ngay ở vòng đầu tiên, chỉ mới cộng một word. Checksum khi đó luôn là ~0x4500 = 0xBAFF bất kể dữ liệu, và dữ liệu bị hỏng cũng không phát hiện được. Nếu len < 2 còn thiếu return (undefined behavior), và byte lẻ bị cộng lặp mỗi vòng.

Bài học: compiler chỉ quan tâm dấu { }, không quan tâm thụt lề. Nên luôn viết ngoặc cho vòng lặp và bật cảnh báo gcc -Wall -Wextra.

Cảnh báo IDE thường gặp ở hai dòng cuối

• Điều kiện là số nguyên thay vì bool: viết while ((sum >> 16) != 0u).
• Thiếu ngoặc quanh thân while: thêm { }.
• Ép kiểu 32 bit xuống 16 bit (-Wconversion): viết (uint16_t)(~sum & 0xFFFFu).

Giới hạn của checksum

Không phát hiện được mọi lỗi, ví dụ đổi chỗ hai word 16-bit hoặc các lỗi bù trừ nhau. Vì vậy các giao thức quan trọng còn dùng thêm CRC32.

7. Bài tập

1. Kiểm tra số chẵn/lẻ bằng x & 1.
2. Đếm số bit 1 trong một số.
3. Kiểm tra lũy thừa của 2: x > 0 && (x & (x - 1)) == 0.
4. Hoán đổi hai biến bằng XOR, không dùng biến tạm.
5. Đảo thứ tự bit trong một byte.
6. Nén 8 giá trị true/false vào một byte.
7. Cộng hex: 0x3A + 0x27 = 0x61, 0xFF + 0x01 = 0x100, 0x4500 + 0x1BB0 = 0x60B0.
8. Hex sang nhị phân: 0x1C = 0001 1100, 0xCA = 1100 1010.
9. Nhị phân sang hex: 11001010 = 0xCA, 101001101 = 0x14D.

Tài liệu tham khảo

• RFC 1071: Computing the Internet Checksum.