Có lẽ bạn hiếm khi cần toán bitwise trong công việc hàng ngày. Toán tử AND/OR bitwise của Ruby (`&` và `|`) thường dùng nhầm hơn là cố ý. Ai chưa từng gõ `&` khi muốn `&&`?
Nhưng nếu bạn lớn lên với ngôn ngữ thấp cấp như C, Assembler, hoặc trong trường hợp của tôi là Turbo Pascal, chắc đã làm việc với bit manipulation.
Giải pháp bitwise rất "cool". Nếu giải quyết bài toán bằng phép toán cơ bản nhất của máy tính (toán học nhị phân), không gì tinh tế hơn.
Làm việc với nhị phân trong Ruby
Bạn biết mọi thứ trong máy tính đều là số, và số ở dạng nhị phân. Nhưng trong Ruby trông như nào? Ví dụ dưới dùng Ruby tra mã ASCII của chữ "a", rồi in dạng "nhị phân".
Dùng phương thức ord lấy mã ASCII, rồi printf in dạng "nhị phân".
Mặc dù phải dùng `printf` để hiển thị nhị phân, bản chất số luôn nhị phân. Bạn viết literal nhị phân trong code bằng cú pháp `0b11111111`.
Để thêm literal nhị phân, tiền tố chuỗi 0/1 bằng 0b. Vậy 0b11111111.
Thao tác giá trị nhị phân
Biết cách dùng literal nhị phân, ta có thể "chơi" với chúng qua các toán tử bitwise.
Bạn quen với toán tử boolean `&&`. Biểu thức `a && b` trả về true chỉ khi cả a và b đều true. Toán tử bitwise rất tương tự.
Ví dụ, bitwise AND so sánh hai giá trị bit theo bit. Nếu cả hai bit đều 1, bit kết quả đặt 1. Ngược lại đặt 0. Với 8 bit, có 8 phép AND riêng biệt. Ví dụ dưới minh họa với 1 bit.
Ví dụ phép bitwise AND với 1 bit.
Tương tự với 2 bit:
Mỗi cặp bit được AND riêng biệt.
Các toán tử Bitwise của Ruby
Gần như mọi ngôn ngữ đều có bộ toán tử này. Nếu chưa quen, hãy thử trong IRB. Một khi nắm vững, bạn dùng được trọn đời.
| Toán tử | Mô tả | Ví dụ |
|---|---|---|
| & | Bitwise AND đặt bit kết quả 1 nếu bit đó là 1 ở cả hai input | 0b1010 & 0b0111 == 0b0010 |
| | | Bitwise OR đặt bit kết quả 1 nếu bit đó là 1 ở một trong hai input | 0b1010 | 0b0111 == 0b1111 |
| ^ | Bitwise XOR đặt bit kết quả 1 nếu bit đó là 1 ở một trong hai input, không phải cả hai | 0b1010 ^ 0b0111 == 0b1101 |
| ~ | Bitwise NOT (Inverse) đảo bit: 1→0, 0→1 | ~0b1010 == 0b0101 |
| << | Left Shift dịch bit trái n vị trí | 0b1010 << 4 == 0b10100000 |
| >> | Right Shift dịch bit phải n vị trí | 0b1010 >> 4 == 0b0000 |
Ứng dụng thực tế: Configuration Flags
Đây có lẽ là cách dùng bitwise math nhàm chán nhất. Nhưng cũng phổ biến nhất. Nếu interface với code Java, C, C++ bạn sẽ gặp bitwise config flags.
Giả sử năm 1996, bạn xây DB từ con số 0. Sau khi xem phim Hackers, quyết định thêm access control.
Có 8 hành động user có thể làm: read, write, delete, và 5 cái khác. Muốn set từng cái độc lập. User có thể read nhưng không write/delete. User khác write nhưng không drop table.
Cách lưu trữ hiệu quả nhất: dùng các bit trong một byte. User OR chúng lại để tạo tổ hợp quyền cần.
MYDB_READ = 0b00000001 # Các số này gọi là bitmasks
MYDB_WRITE = 0b00000010
MYDB_DELETE = 0b00000100
MYDB_INDEX = 0b00001000
user.permissions = MYDB_READ | MYDB_WRITE
Điều này tương tự Unix file permissions. Nếu từng thắc mắc tại sao cần "magic number" để làm file read-only, bây giờ bạn biết.
Lưu config trong bit vô nghĩa nếu không detect bit nào được set. Dùng bitwise AND:
Dùng AND với bitmask để xác định bit có được set không.
Ứng dụng ít thực tế hơn (Trừ khi bạn là C programmer)
Bây giờ làm vài trò "ma thuật toán học".
Lịch sử, bit manipulation dùng khi nén từng phân giây tính toán. Do đó đồ họa và người cần hiệu năng tối đa dùng nhiều.
Kỹ thuật này không thực tế cho Ruby development hàng ngày. Nhưng vẫn bài tập thú vị, và có thể hữu ích thật nếu bạn vào embedded systems. Xem danh sách bit twiddling hacks để sâu hơn.
Nhân & Chia cho lũy thừa của 2
Xem biểu diễn nhị phân của 1, 2, 4, 8. Nhận thấy: nhân 2 ≡ dịch trái 1 bit. Chia 2 ≡ dịch phải 1 bit.
Biểu diễn nhị phân của 1, 2, 4, 8.
Có toán tử shift-left/right, nên nhân/chia lũy thừa 2 chỉ bằng dịch bit.
Dùng bitwise shift operator nhân/chia lũy thừa 2.
Trung bình hai số nguyên dương
Cộng hai số: `(x+y) == (x&y)+(x|y) == (x^y)+2*(x&y)`. Để trung bình, chỉ cần chia 2 — lấy right shift.
Trung bình hai số nguyên dương: (x&y)+((x^y)>>1).
Fast Inverse Square Root
Không thể viết bài bit twiddling mà thiếu ví dụ huyền thoại: Fast inverse square root của John Carmack, từ source Quake 3 Arena 1999. Thuật toán không phải của ông, nhưng implementation nổi tiếng nhất.
Không port trực tiếp sang Ruby, vì nó xây dựng biểu diễn nhị phân float theo cách không dịch chuyển trực tiếp từ C sang Ruby.
float Q_rsqrt( float number ) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, can remove
return y;
}