Sử dụng bit và bitwise để xây dựng ứng dụng

Dùng bitwise là một cách tuyệt vời, cực kì tối ưu cả về tốc độ tính toán lẫn sử dụng bộ nhớ. Nhưng có vẻ không nhiều developer hiện nay biết và ứng dụng nó. Bài này đưa ra ba trường hợp thực tế sử dụng bit và bitwise để xử lý. Github repo: https://github.com/refacore/bitwise

Lưu và xử lý quyền truy nhập

Thay vì lưu thành các giá trị riêng biệt, các quyền được lưu thành 1 bit trong 1 byte dữ liệu. Một bản ghi phân quyền trên tài nguyên sẽ là 4 bit cho 4 quyền phổ biến: Read, Write, Execute, Denied, tương đương 0b0000. Nếu người dùng được cấp nhiều role khác nhau, có nhiều bản ghi phân quyền khác nhau, việc tổng hợp lại các bản ghi này cũng rất dễ dàng và nhanh chóng. Chúng ta chỉ việc AND tất cả các bản ghi lại với bản ghi có quyền tương ứng. Ví dụ cần kiểm tra quyền Write, bản ghi quyền Write mặc định là 0b0100 (theo thứ tự được quy định phía trên). Dù có bao nhiều bản ghi thì nếu OR tất cả lại và AND với bản ghi Write mặc định này, kết quả sẽ luôn bẳng bản ghi Write mặc định nếu có quyền, hoặc 0 nếu không có quyền. Dễ dàng và nhanh chóng hơn việc tổng hợp các giá trị riêng lẻ. Chúng ta cũng có thể kiểm tra nhiều quyền cùng lúc mà không tăng độ phức tạp. Ví dụ cần kiểm tra cả quyền Write và Execute, bản ghi mặc định là 0b0110. Dùng phép AND với tất cả bản ghi mà kết quả vẫn bằng 0b0110 thì là thỏa mãn. Nếu lưu quyền dưới dạng một mảng, ta phải thực hiện vòng lặp hai lần để kiểm tra 2 quyền này.

Mã nguồn phần mô tả này nằm trong thư mục PermissionValidation. Các quyền được liệt kê dưới dạng 1 enum cho dễ đọc. Cách làm này khá phổ biến trong thư viện dotnet nếu các bạn để ý.

public enum Permissions
{
    Read = 0x1,
    Write = 0x2,
    Execute = 0x4,
    Denied = 0x8,
}

Để lưu lại quyền Read, Write của user trên một tài nguyên, chúng ta OR 2 giá trị tương ứng của enum

Permissions = Permissions.Read | Permissions.Write

Mặc dù mang 2 giá trị nhưng kích thước vẫn là Integer 32 bit. 0b01 | 0b11 = 0b11 (3 dạng thập phân) Để kiểm tra có quyền Read hay Write hay không, ta AND với giá trị enum tương ứng

CanRead = (permissions) => (permissions & Permissions.Read) == Permissions.Read

User có nhiều role, ta OR các role lại rồi lại AND với giá trị enum

CanRead = (permissions: Permissions[]) => (permissions.aggregate((p1, p2) => p1 | p2) & Permissions.Read) == Permissions.Read

Game

Một mảng hay một ma trận các bit là cách lưu state của game tuyệt vời. Mã nguồn dùng trò Bắn tàu để minh họa. Bạn sẽ thấy dùng bit ưu việt thế nào so với việc dùng một mảng 2 chiều các số nguyên để lưu bản đồ. Đối với các board game cần tìm các mẫu thỏa mãn cho trước, dùng các bit để lưu giúp việc matching các mẫu nhanh gọn, dễ dàng hơn hẳn (nếu dùng các mảng hai chiều, bạn phải thực hiện vòng lặp, còn với các bit, các phép bitwise cực tiết kiệm và ngắn gọn).

public class Map
{
    public byte[] Rows { get; set; } = { 0, 0, 0, 0, 0, 0, 0, 0 };
}

public void Shoot(int x, int y)
{
    var rowOnMap = map.Rows[x];

    var rowOnShoot = (byte)1 << y;

    if ((rowOnMap & rowOnShoot) == rowOnShoot)
    {
        Console.WriteLine("Accurate!");
    }
    else
    {
        Console.WriteLine("Missed");
    }
}

Một ví dụ khác với trò cờ Caro. Lưu mỗi nước đi của kì thủ vào mảng long 64 phần tử, bạn đã có một bàn cờ 64x64. Để test checkmate, chúng ta chỉ cần shift (2ˆ5 - 1) đến tọa độ của nước đi và dùng phép AND để kiểm tra các trường hợp. Nhanh hơn và tiết kiệm bộ nhớ hơn nhiều so với lưu một struct trong một mảng hai chiều. (Test checkmate với hàng thì đã rõ ràng. Việc làm phép xoay map để test checkmate với cột và đường chéo có thể thực hiện đơn giản bằng các phép OR và shift với 10 row xung quanh nước đi. Các bạn có thể thử tính toán một chút xem).

Cộng dồn các options

Kĩ thuật này khá là phổ biến trong các thư viện hay framework nhưng lại không mấy khi được các lập trình viên học lại trong ứng dụng của mình. Liệt kê các lựa chọn của một hàm nào đó là dạng bit. Khi bạn thực hiện OR giữa các options, các option này đều được thể hiện trong số int ấy. Ví dụ lựa chọn Món Cá là 1 0b01, món Bò là 2 0b10. OR 2 món trên ta có số 3 là 0b11. AND với Cá thì sẽ cho ra Cá, AND với Bò thì sẽ cho ra Bò.

Mã nguồn giả định xay dựng NotificationService mà người dùng có quyền lựa chọn nhận tin nhắn qua các kênh Email, SMS hoặc Mobile app notification. Với enum được khai báo như sau:

public enum NotificationChannels
{
    None = 0,
    Email = 0x1,
    Sms = 0x2,
    Mobile = 0x4,
    All = 0x7
}

Một Factory có thể lấy ra các instance của sender tương ứng mỗi option bằng cách kiểm tra đơn giản:

public IEnumerable<INotificationSender> GetSenders(NotificationChannels channels)
{
    var senders = this.serviceProvider.GetServices<INotificationSender>();

    if (channels == NotificationChannels.All)
    {
        return senders;
    }

    return senders.Where(sender => (sender.Channel & channels) == sender.Channel);
}

Trên đây là một số chia sẻ hi vọng có ích với các bạn mới vào nghề. Mặc dù sự phát triển của ngôn ngữ và năng lực tính toán khiến sự quan tâm của các dev chuyển dịch lên các marco cấp cao, bit - bitwise vẫn là nền tảng và sử dụng nó cũng rất thú vị.