Dịch bit là gì?
Dịch bit (bit shift) là thao tác dời các chữ số nhị phân của một số nguyên sang trái hoặc sang phải một số vị trí nhất định. Đây là một phép tính nền tảng trong lập trình, tối ưu hóa cấp thấp, xử lý đồ họa, băm dữ liệu (hashing) và hệ thống nhúng. Phép dịch trái (n << k) đẩy các bit về phía trọng số cao nhất và thêm số 0 vào phía sau, còn phép dịch phải (n >> k) đẩy các bit về phía trọng số thấp nhất.
Cách dùng công cụ này
Bạn nhập số nguyên n, số bit cần dịch k, rồi chọn hướng dịch. Công cụ sẽ trả về kết quả dưới dạng giá trị thập phân. Công cụ này dùng số nguyên có dấu 64-bit, đúng như cách hầu hết các ngôn ngữ lập trình xử lý.
Giải thích công thức
Mỗi lần dịch trái một vị trí sẽ làm số đó tăng gấp đôi, nên dịch trái k vị trí tương đương với nhân cho \(2^{k}\): $$\text{Result} = \text{Number (n)} \ll \text{Shift (k)} = n \times 2^{k}$$ Ngược lại, mỗi lần dịch phải một vị trí sẽ làm số đó giảm một nửa kèm cắt bỏ phần dư, nên dịch phải k vị trí chính là phép chia nguyên cho \(2^{k}\): $$\text{Result} = \text{Number (n)} \gg \text{Shift (k)} = \left\lfloor \frac{n}{2^{k}} \right\rfloor$$ Đây là lý do phép dịch bit "rẻ" hơn nhiều so với phép nhân hay phép chia trên phần cứng.
Ví dụ minh họa
Lấy \(n = 16\) và dịch trái với \(k = 2\). Ở dạng nhị phân, 16 là 10000. Dịch trái hai vị trí sẽ thêm hai số 0 vào sau: 1000000, tức là 64. Về mặt toán học, $$16 \times 2^{2} = 16 \times 4 = 64$$ Theo chiều ngược lại, $$64 \gg 2 = \left\lfloor \frac{64}{4} \right\rfloor = 16$$ trả về đúng giá trị ban đầu.
Bảng Tham Chiếu Lũy Thừa Của Hai
Dịch trái đi \(k\) vị trí nhân một số với \(2^k\); dịch phải đi \(k\) vị trí chia cho \(2^k\) (bỏ dư lấy phần nguyên cho số nguyên). Sử dụng bảng này để đọc ngay bộ nhân hoặc bộ chia cho một lượng dịch nhất định.
| Dịch \(k\) | \(2^k\) (thập phân) | Ý nghĩa của \(\ll k\) / \(\gg k\) |
|---|---|---|
| 0 | 1 | không thay đổi |
| 1 | 2 | \(\times 2\) / \(\div 2\) |
| 2 | 4 | \(\times 4\) / \(\div 4\) |
| 3 | 8 | \(\times 8\) / \(\div 8\) |
| 4 | 16 | \(\times 16\) |
| 5 | 32 | \(\times 32\) |
| 6 | 64 | \(\times 64\) |
| 7 | 128 | \(\times 128\) |
| 8 | 256 | \(\times 256\) (1 byte) |
| 9 | 512 | \(\times 512\) |
| 10 | 1,024 | \(\times 1024\) (1 KiB) |
| 11 | 2,048 | \(\times 2048\) |
| 12 | 4,096 | \(\times 4096\) |
| 13 | 8,192 | \(\times 8192\) |
| 14 | 16,384 | \(\times 16384\) |
| 15 | 32,768 | \(\times 32768\) |
| 16 | 65,536 | \(\times 65536\) (2 byte) |
| 17 | 131,072 | |
| 18 | 262,144 | |
| 19 | 524,288 | |
| 20 | 1,048,576 | \(\times\) 1 MiB |
| 32 | 4,294,967,296 | ranh giới 32-bit |
| 63 | 9,223,372,036,854,775,808 | bit cao nhất của một số nguyên có dấu 64-bit |
Câu hỏi thường gặp
Dịch trái có bao giờ làm mất dữ liệu không? Có — những bit bị đẩy vượt ra ngoài độ rộng của số nguyên sẽ bị loại bỏ (tràn số). Trong phạm vi 64-bit, công cụ này vẫn giữ nguyên giá trị.
Số âm khi dịch phải thì sao? Công cụ này dùng phép dịch phải số học (có dấu), nên bit dấu được giữ lại và số âm vẫn là số âm.
Tại sao nên dùng dịch bit thay cho nhân hoặc chia? Trên đa số CPU, phép dịch bit chỉ tốn một chu kỳ xử lý, nên đây là cách rất nhanh để nhân hoặc chia cho các lũy thừa của 2.
