Phép toán thao tác bit (bitwise operation) và ứng dụng trong lập trình, thiết kế hệ thống

I. Giới thiệu phép toán thao tác bit

Về mặt toán học các phép toán thao tác bit (bitwise), các bạn có thể tham khảo tại đây.

Đây là phép toán cơ bản trong máy tính, chắc các bạn cũng biết để tạo ra phép cộng, trừ, nhân, chia trong toán học cũng cần ghép nhiều lần các phép toán này (Tham khảo).

Vậy nên khi sử dụng nó, tốc độ xử lý trong lập trình sẽ tốt hơn các operator, method khác rất nhiều

Trong bài viết này, về ký hiệu phép toán mình sẽ dùng ký hiệu của đa số ngôn ngữ thông dụng hiện nay như js, php, python, …

Phép toán bitwise

II. Ứng dụng của nó trong việc giải quyết bài toán tập hợp:

1. LIÊN HỆ XỬ LÝ TẬP HỢP

Sau khi xem mô tả lý thuyết, có vẻ ít người nhận ra được tác dụng của nó để ứng dụng các bài toán thực tế.
Ở bài viết này mình muốn nhắc đến việc ứng dụng nó vào các phép toán tập hợp ( phép giao và phép hợp và …)
Khi ta coi mỗi vị trí bit 1 của 1 số biểu thị cho sự hiện diện cho 1 phần tử trong tập hợp.

Ví dụ trường hợp đặt hằng số đại diện 12 con giáp này trong lập trình:

• Cách bình thường mọi người hay đặt:
  (Tý: 1, Sửu: 2, Dần: 3, Mão: 4, …, Hợi:12)
• Cách đặt để có thế ứng dụng phép bitwise:
  (Tý: 1<<0, Sửu: 1<<1, Dần: 1<<2, Mão: 1<<3, …, Hợi: 1<<11)
  Chú thích: đặt như vậy để xác định các tập hợp trên không hề giao nhau và đều khác 0 (tức là tập rỗng)

Tập hợp nhiều con giáp:

• Cách bình thường(1 mảng): [1,2,3,4,..,12]
• Cách bitwise(1 số int): 1|2|4|8|…|2048 = 4095

2. Các phép toán tập hợp

a. Phép giao (Intersection): Khi thực hiện phép a & b, ta có thể thu được biểu diễn bit của kết quả phép A ∩ B. (A ∩ B  <=>a & b)

Ví dụ:
Tập hợp A có Tý, Sửu, Dần (giá trị binary a là 111)
Tập hợp B có Tý, Sửu, Mão (giá trị binary b là 1011)
–> A ∩ B sẽ có Tý, Sửu (tương ứng với giá trị binary a & b là 11)

b. Phép thuộc: (trường hợp con của phép giao bên trên)

Ví dụ:
Tập hợp A có Tý, Sửu, Dần (giá trị binary a là 111)
x là Sửu (giá trị binary b là 10)
–> x ∩ A sẽ có Sửu (tương ứng với giá trị binary x & a là 10)

c. Phép hợp (Union): Khi thực hiện phép a | b, ta có thể thu được biểu diễn bit của kết quả phép A  ∪  B. (A ∪ B  <=> a | b)

VD:
Tập hợp A có Tý, Sửu, Dần (giá trị binary a là 111)
Tập hợp B có Tý, Sửu, Mão (giá trị binary b là 1011)
–> A  ∪  B sẽ có Tý, Sửu, Dần, Mão (tương ứng với giá trị binary a|b là 1111)

d. Phép Hiệu (Difference): Khi thực hiện phép a ^ (a&b), ta có thể thu được biểu diễn bit của kết quả phép A  \  B (A \ B <=> a ^ (a & b))

VD:
Tập hợp A có Tý, Sửu, Dần (giá trị binary a là 111)
Tập hợp B có Tý, Sửu, Mão (giá trị binary b là 1011)
–> A \  B sẽ có Dần (tương ứng với giá trị binary a^(a&b) là 100)

3. Khác biệt với cách bình thường

Bình thường, chúng ta cần duyệt it nhất 1 trong 2 tập hợp(array)  A hoặc B mới có thể xử lý được các phép toán trên. Tương ứng với độ phức tạp O(n)

Dùng phương pháp này, chúng ta sẽ cải thiện được khá nhiều về tốc độ xử lý và tối ưu lưu trữ.

III. Ứng dụng thiết kế Database khi lập trình

Mình lấy ví dụ với hệ thống thực tế khi lưu thứ (thứ 2, 3, 4, .., 8 là chủ nhật) để biểu diễn việc nhân viên đã đăng ký làm những thứ nào

1. Thiết kế Database

• Đặt các hằng số đại diện các thứ (vì số lượng cố định nên không cần thiết lưu thành bảng trong DB)

define('MONDAY', 1); define('MONDAY_BITWISE', 1<<(MONDAY - 1)); // 1
define('TUESDAY', 2); define('TUESDAY_BITWISE', 1<<(TUESDAY - 1)); // 2
define('WEDNESDAY', 3); define('WEDNESDAY_BITWISE', 1<<(WEDNESDAY - 1)); // 4
define('THURSDAY', 4); define('THURSDAY_BITWISE', 1<<(THURSDAY - 1)); // 8
define('FRIDAY', 5); define('FRIDAY_BITWISE', 1<<(FRIDAY - 1)); // 16
define('SATURDAY', 6); define('SATURDAY_BITWISE', 1<<(SATURDAY - 1)); //32
define('SUNDAY', 7); define('SUNDAY_BITWISE', 1<<(SUNDAY - 1)); //64
define('ALL_WEEK_BITWISE', MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE | THURSDAY_BITWISE | FRIDAY_BITWISE | SATURDAY_BITWISE | SUNDAY_BITWISE);

• Bảng employee lưu thông tin những nhân viên trong công ty (id, name, weekdays_work)
• Bảng employee_weekdays_work để lưu nhân viên làm việc những ngày nào trong trường hợp không xử lý bitwise

Để biểu thị nhân viên đăng ký làm những thứ nào trong tuần chúng ta dùng cột weekdays_work (thay vì tạo 1 bảng riêng như các trường hợp bình thường)

2. Xử lý 1 số logic tương ứng

a. Khởi tạo dữ liệu

ví dụ:

• Nhân viên A có id là 1 làm việc thứ 2, 3, 4
• Nhân viên B có id là 2 làm việc thứ 2, 4, 6
• Nhân viên C có id là 3 làm việc thứ 4, 5, 6
• Nhân viên D có id là 4 làm việc thứ 7, chủ nhật
• Nhân viên E có id là 5 làm việc thứ 3, 5, 7

$employee_A = Employee($id = 1, $name = 'A', $weekdays_work = MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE); // Nhân viên A có id là 1 làm việc thứ 2, 3, 4
$employee_B = Employee($id = 2, $name = 'B', $weekdays_work = MONDAY_BITWISE | WEDNESDAY_BITWISE | FRIDAY_BITWISE); // Nhân viên B có id là 2 làm việc thứ 2, 4, 6
$employee_C = Employee($id = 3, $name = 'C', $weekdays_work = WEDNESDAY_BITWISE | THURSDAY_BITWISE | THURSDAY_BITWISE); // Nhân viên C có id là 3 làm việc thứ 4, 5, 6
$employee_D = Employee($id = 4, $name = 'D', $weekdays_work = SATURDAY_BITWISE | SUNDAY_BITWISE); // Nhân viên D có id là 4 làm việc thứ 7, chủ nhật
$employee_E = Employee($id = 5, $name = 'E', $weekdays_work = TUESDAY_BITWISE | THURSDAY_BITWISE | SATURDAY_BITWISE); // Nhân viên E có id là 5 làm việc thứ 3, 5, 7

b. Xử lý các vấn đề thực tế

• Select những nhân viên làm việc thứ 2, thứ 3, thứ 4

(MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE = 7):

SELECT * FROM employee WHERE (weekdays_work & 7);

• Select những nhân viên không làm việc thứ 2, thứ 3, thứ 4

(MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE = 7):

SELECT * FROM employee WHERE !(weekdays_work & 7);

• Tìm những thứ làm việc cùng nhau của 2 nhân viên A và B

$weekdays_work = $employee_A->weekdays_work & $employee_B->weekdays_work;

Gọi sql sau để tìm ra những nhân viên làm những ngày có cả A và B:

SELECT * FROM employee WHERE (weekdays_work & $weekdays_work);

• Tìm những thứ có ít nhất 1 quản lý đi làm (ví dụ chỉ có A và B là quản lý)

$weekdays_work = $employee_A->weekdays_work | $employee_B->weekdays_work;

• Tìm những thứ không có quản lý nào đi làm (ví dụ chỉ có A và B là quản lý)

$weekdays_work = ALL_WEEK_BITWISE ^ ($employee_A->weekdays_work | $employee_B->weekdays_work);

IV. Tổng kết

• Nên dùng bitwise với những trường hợp có nhiều logic tập hợp
• Dùng bitwise trong trường hợp số lượng phần tử vừa phải, không quá nhiều vì nếu nhiều phần tử quá thì giá trị để biểu thị phần tử sẽ rất lớn (1<<30 lớn hơn 1 tỷ )
• Cải thiện được nhiều về tốc độ, xử lý nhanh gọn hơn, lưu dữ liệu gọn hơn
• Nhưng khi duyệt tập hợp từng phần tử lẻ từ bitwise sẽ tốn công hơn chút.