Đâ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 ().

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)

Như đã nói ở trên, ngôn ngữ lập trình C là một ngôn ngữ lập trình hệ thống. Do đó, nó cho phép các thao tác trên số nhị phân. Đối với những người làm việc liên quan đến lập trình hệ thống và giao diện máy tính, các toán tử trên số nhị phân cho phép họ truy cập vào bộ nhớ mà không cần phải viết mã nguồn theo ngôn ngữ máy, Tuy nhiên, trong những công việc thường ngày, những toán tử này ít được dùng . Trước khi đi vào chi tiết về những thao tác và các toán tử hiện tại đang có trong C, chúng ta hãy thảo luận một số điều căn bản sau đây:

Máy tính có thể hiểu được hệ thống số nhị phân. Hệ nhị phân có nghĩa là hệ thống gồm hai chữ số. Hệ nhị phân bao gồm số 0 và 1. Tôi cho rằng sinh viên ở đây đã khá quen thuộc với những hệ thống số học khác nhau cũng như cách chuyển đổi từ hệ thâp phân sang hệ nhị phân và ngược lại.

Trong hầu hết các hệ thống máy tính, một byte có tám bít. Mỗi bít có thể là 0 hoặc 1. Do đó, một byte là một chuỗi của những số 0 và 1. Bít ngoài cùng bên phải của chuỗi byte được gọi là bít có trọng số bé nhất và bít ngoài cùng bên trái được gọi là bít có trọng số lớn nhất. Số âm được miêu tả theo một cách khác. (Nhớ rằng, một số nguyên có thể có dấu hoặc không dấu.) Nếu như bít ngoài cùng bên trái là bít dấu và nếu nó là 1 thì chữ số đó là số âm, nếu nó là 0 thì đó là số dương.

Toán tử trên bít theo như tên gọi gợi ý, nó được dùng để thực hiện những thao tác trên cái số nhị phân. Những toán tử nhị phân có trong C được giới thiệu phía dưới đây:

& Toán tử AND | Toán tử OR ^ Toán tử EXOR ~ Toán tử biểu diễn phần bù 1 << Dịch trái >> Dịch phải

 Bảng 11.1

Các toán tử logic trên bit

Thao tác luận lý cho hai kết quả, đó là đúng hoặc sai. Trong ký hiệu nhị phân, số 1 thể hiện cho Đúng và số 0 thể hiện cho sai. Một số nguyên được lưu trữ trong bộ nhớ có thể được xem như một chuỗi của những giá trị đúng và sai.

Những toán tử logic trên bít hoạt động trên những toán hạng mà theo đó có nhiệm vụ thực hiện tính toán trên từng từng bit để cho ra kết quả của một số nguyên.

Toán tử thao tác bit AND

Toán tử AND sẽ trả về giá trị là Đúng (1), nếu và chỉ nếu cả hai toán hạng đều có giá trị là 1.

0 & 0 0 0 & 1 0 1 & 0 0 1 & 1 1

Bảng 11.2

Chương trình 11.1

/* Chương trình để minh họa cho toán tử AND */

include

main () {     int a = 25;     int b = 77;     int c;     c = a & b;     printf("Value of c is %d\n", c); }

Kết quả của chương trình như sau :

Giá trị của c là 9.

Toán tử AND xảy ra được thể hiện dưới đây:

0000000000011001 25 0000000001001101 77 0000000000001001 9

Table 11.3

Toán tử AND được sử dụng cho những thao tác mặt nạ . Toán tử này có thể được dùng để gán số 0 vào một số bít đặc biệt. Bạn cũng có thể sử dụng toán tử AND để kiểm tra xem một số nguyên là số lẻ hay chẵn. Khi bạn tiến hành toán tử AND trên một số nguyên với 1, thì kết quả luôn luôn là đúng nếu bít ngoài cùng bên phải của số nguyên đó là 1. Đây là trường hợp của số nguyên lẻ, đối với trường hợp số nguyên chẵn thì bít ngoài cùng bên phải sẽ là số 0.

Toán tử OR

Trong thao tác OR cũng vậy, chuỗi nhị phân của hai toán hạng được so sánh theo từng bít. Mỗi bít trong toán hạng đầu là 1 hoặc mỗi bít trong toán hạng thứ hai sẽ là 1 sẽ cho ra 1 trong bít tương ứng trong kết quả.

0 | 0 0 0 | 1 1 1 | 0 1 1 | 1 1

Bảng 11.3

Toán tử OR được dùng khi bạn muốn gán số 1 cho một vài bít đặc biệt nào đó.

Toán tử XOR

Toán tử XOR sẽ cho ra 1 nếu một trong hai bít là số 1 nhưng không phải cả hai.

0 ^{0 0 0} 1 1 1 ^{0 1 1} 1 0

Bảng 11.4

Một điều quan trọng đáng chú ý đó là bất cứ giá trị nào khi đã được XOR với chính nó sẽ cho ra kết quả là 0. Những người lập trình ngôn ngữ Assembly thường vận dụng điều này để kiểm chứng hai giá trị có bằng nhau không.

Toán tử phần bù số 1

Toán tử phần bù số 1 trong C được miêu tả như dấu ngã ~ Nó sẽ phủ định luận lí từng bit của toán hạng của nó, Nói theo cách khác, tất cả những giá trị 0 sẽ trở thành 1 và những giá trị 1 sẽ trở thành 0. Đây là toán tử một ngôi được dùng trên một hằng số nguyên hoặc trên một biểu thức.

Ví dụ

~ 12 ~ (Total - 2)

Ở đây, Total phải là một số nguyên

Toán tử phần bù được dùng để giúp chương trình linh động hơn. Ví dụ như, nếu chúng ta muốn gán giá trị của bít ngoài cùng bên phải của một số nguyên cho 0 trên cả hai máy 16 bít và 32 bít, một cách khôn ngoan đó là chúng ta AND số đó với một số bù của nó.

Total& = ~1;

Nó sẽ trả kết quả ở dạng của số bù 1 với tất cả những bít 1 ở ngoài cùng bên trái cần thiết để lấp đầy kích cỡ của số nguyên. Nó sẽ bao gồm 15 số bít ở ngoài cùng bên trái trên một máy có 16 bít số nguyên, và 31 bít trên một máy với 32 bít số nguyên.

Toán tử dịch chuyển

Toán tử dịch trái hay dịch phải tương đồng với phép nhân và chia cho 10. Khi chúng ta chia một số cho 10, chúng ta sẽ dịch chuyển những con số một lần về phía phải bằng cách giữ lại dấu chấm thập phân. Khi chúng ta nhân một số với 10, chúng ta dịch các số về bên trái và thêm vào số 0 bên phải.

Toán tử dịch trái <<

Khi toán tử dịch trái được thực hiện trên một toán hạng, những bit của toán hạng được dịch về bên trái. Các bít bị chuyển sang trái bị mất và 0 thay vào phía bên phải của toán hạng.

If Salary là một biến với giá trị trong hệ bát phân là 6 , thì toán tử dịch trái sẽ cho ra kết quả là 14 trong hệ bát phân.

Chương trình 11.2

/* Chương trình minh họa cho toán tử dịch bít trái */

include

main () {     unsigned int salary = 06;     salary <<=1;     printf("Value of salary is %o\n", salary); }

Toán tử dịch bit phải >>

Trong thao tác dịch bít phải, bít ở bên phải bị dịch chuyển sẽ bị mất và tùy thuộc vào loại của máy tính, số 1 hay số 0 sẽ được thêm vào ở bít ngoài cùng bên trái. Toán tử dịch chuyển cũng thường được nhắc đến như xoay trái và xoay phải.