Text of Relipa

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

luandt

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:

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

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

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);

Để 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ụ:

$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ế

(MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE = 7):

SELECT * FROM employee WHERE (weekdays_work & 7);

(MONDAY_BITWISE | TUESDAY_BITWISE | WEDNESDAY_BITWISE = 7):

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

$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);
$weekdays_work = $employee_A->weekdays_work | $employee_B->weekdays_work;
$weekdays_work = ALL_WEEK_BITWISE ^ ($employee_A->weekdays_work | $employee_B->weekdays_work);

IV. Tổng kết