Tài liệu

Phép toán thao tác bit trong C++ (Bitwise operation)

avatar
Huy Erick
00:00 12/04/2024

Trong bài viết này, chúng ta sẽ khám phá về phép toán thao tác bit (bitwise operation). Trong đơn vị logic số học (nằm trong CPU), các phép toán như cộng, trừ, nhân và chia...

Trong bài viết này, chúng ta sẽ khám phá về phép toán thao tác bit (bitwise operation). Trong đơn vị logic số học (nằm trong CPU), các phép toán như cộng, trừ, nhân và chia được thực hiện ở cấp độ bit. Để thực hiện các phép toán cấp độ bit trong C++, chúng ta sử dụng các toán tử bitwise.

Hình ảnh biểu diễn các con số 0 và 1 trích từ bộ phim nổi tiếng Ma trận (The Matrix)

Trước khi đi vào các bài tập ví dụ, chúng ta hãy ôn lại một chút kiến thức về các phép toán logic, bao gồm 6 phép toán cơ bản:

Xem thêm:

Các phép toán thao tác bit cơ bản

Phép toán AND (&)

Kết quả của phép AND sẽ là 1 nếu cả 2 toán hạng là 1. Nếu một trong hai toán hạng là 0 thì kết quả sẽ là 0, sau đây là bảng chân trị của phép AND:

A B A & B
0 0 0
0 1 0
1 0 0
1 1 1

Ví dụ phép AND giữa 2 số thập phân là 5 và 3:

0101 (5) & 0011 (3) = 0001 (1)

Minh họa với C++:

#include 
using namespace std;

int main() {
    int a = 5;
    int b = 3;
    int result = a & b;

    cout  "Kết quả: "  result  endl;

    return 0;
}

Kết quả:

Kết quả: 1

Phép toán OR (|)

Kết quả của phép OR sẽ là 1 nếu một trong hai toán hạng là 1. Trong C++, phép OR được ký hiệu là |. Dưới đây là bảng chân trị của phép OR:

| A | B | A | B | |---|---|-----| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

Ví dụ phép OR của 12 và 25:

00001100 (12) | 00011001 (25) = 00011101 (29)

Minh họa với C++:

#include 
using namespace std;

int main() {
    int a = 12;
    int b = 25;
    int result = a | b;

    cout  "Kết quả: "  result  endl;

    return 0;
}

Kết quả:

Kết quả: 29

Phép toán XOR (^)

Kết quả của phép XOR là 1 nếu 2 toán hạng có giá trị khác nhau.

A B A ^ B
0 0 0
0 1 1
1 0 1
1 1 0

Ví dụ phép XOR giữa 2 số thập phân là 5 và 3:

0101 (5) ^ 0011 (3) = 0110 (6)

Minh họa với C++:

#include 
using namespace std;

int main() {
    int a = 5;
    int b = 3;
    int result = a ^ b;

    cout  "Kết quả: "  result  endl;

    return 0;
}

Kết quả:

Kết quả: 6

Ngoài ra, có 2 tính chất đặc biệt với phép XOR:

  • A ^ A = 0 (1 toán hạng XOR với chính nó sẽ bằng 0)
  • A ^ 0 = A (Bất kỳ toán hạng nào XOR với 0 đều bằng chính nó)

Phép toán NOT (~)

Toán tử NOT là toán tử 1 ngôi. Nó thay đổi toán hạng từ 0 sang 1 và ngược lại.

A ~A
0 1
1 0

Ví dụ:

~ 00011110 (30) = 11100001 (225)

Minh họa với C++:

#include 
using namespace std;

int main() {
    int a = 30;
    int result = ~a;

    cout  "Kết quả: "  result  endl;

    return 0;
}

Kết quả:

Kết quả: -31

Chúng ta thấy kết quả của ~30 là -31 thay vì 225, tại sao lại như vậy?

Để hiểu điều này, chúng ta sẽ nói qua một chút về bù 2 (2’s complement):

Bù 2 của một số sẽ bằng bù 1 (~) của số đó cộng thêm 1.

Đối với bất kỳ số nguyên n, thì ~n sẽ bằng -(n+1). Vì ~n được biểu diễn dưới dạng bù 2 và bù 2 của ~n sẽ là -(~(~n)+1)=-(n+1).

Suy ra kết quả ở đây sẽ là -31 thay vì 225 vì bù 1 của 30 (~30) là 225, bù 2 của 225 là -31.

Toán tử dịch bit

Dịch phải (>>)

Toán tử dịch phải bit sẽ dịch tất cả các bit sang phải bởi một số nhất định.

Dịch trái ()

Toán tử dịch trái bit sẽ dịch tất cả các bit sang trái bởi một số nhất định.

212 = 11010100 (Số nhị phân)
2121 = 11010100 (Số nhị phân) (Dịch sang trái 1 bit)
2120 = 11010100 (Giữ nguyên)
2124 = 11010100 (Số nhị phân) (Dịch sang trái 4 bit)

Minh họa với C++:

#include 
using namespace std;

int main() {
    int num = 212, i;

    for(i = 0; i=2; i++) {
        cout  "Dịch sang phải "  i  " bits: "  (num>>i)  endl;
    }

    cout  endl;

    for(i = 0; i=2; i++) {
        cout  "Dịch sang trái "  i  " bits: "  (num endl;
    }

    return 0;
}

Kết quả:

Dịch sang phải 0 bits: 212
Dịch sang phải 1 bits: 106
Dịch sang phải 2 bits: 53

Dịch sang trái 0 bits: 212
Dịch sang trái 1 bits: 424
Dịch sang trái 2 bits: 848

Bài tập phép toán thao tác bit

Bạn có thể thực hành các bài tập liên quan tới phép toán thao tác bit (bitwise) trên nền tảng Luyện Code. Sau đây sẽ là 2 bài toán kinh điển có sự hỗ trợ của phép toán thao tác bit đi kèm hướng dẫn và lời giải tham khảo sử dụng C++.

Kiểm tra tính chẵn lẻ của một số

Đề bài: Cho 1 số nguyên n, kiểm tra xem n là chẵn hay lẻ?

Chúng ta sẽ thấy rằng những số chẵn ở dạng nhị phân thì bit ngoài cùng bên phải sẽ luôn là bit 0, đối với số lẻ thì bit ngoài cùng bên phải sẽ luôn là 1. Dựa vào điều này ta có thể dễ dàng biết tính chẵn lẻ bằng cách lấy số đó AND(&) với 1. Nếu kết quả bằng 1 thì đó là số lẻ, ngược lại nếu bằng 0 thì số đó là chẵn. Ví dụ:

0100 (4) & 0011 (3) = 0000 (0)
0101 (5) & 0001 (1) = 0001 (1)

Lời giải tham khảo với C++:

#include 
using namespce std;

int main() {
    int n = 9;

    if(n & 1 == 1) {
        cout  "Lẻ";
    } else {
        cout  "Chẵn";
    }

    return 0;
}

Tìm số xuất hiện 1 lần duy nhất trong mảng

Đề bài: Cho 1 mảng các số nguyên, mỗi số trong mảng xuất hiện 2 lần, ngoại trừ 1 số xuất hiện đúng 1 lần, hãy tìm số xuất hiện đúng 1 lần đó.

Đối với bài toán này chúng ta có khá nhiều cách giải, có thể sử dụng hash table, độ phức tạp thời gian sẽ là O(n) nhưng lại yêu cầu nhiều bộ nhớ hơn. Vậy ở đây chúng ta sẽ sử dụng các phép toán bit với độ phức tạp thời gian là O(n) và không gian là O(1).

Như đã đề cập ở phần XOR(^), phép XOR có 2 tính chất đặc biệt, và ý tưởng cho bài toán này là chúng ta chỉ cần XOR hết tất cả các phần tử trong mảng lại với nhau, 2 phần tử trùng nhau sẽ trả về về 0 và còn lại phần tử xuất hiện đúng 1 lần sẽ XOR với 0 và trả về phần tử đó.

Giả sử có mảng arr như sau: arr = [2, 3, 5, 4, 5, 3, 4]. Thực hiện XOR tất cả các phần tử với nhau:

2 ^ 3 ^ 5 ^ 4 ^ 5 ^ 3 ^ 4
= 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 5 (đổi vị trí cho dễ nhìn)
= 2 ^ 0 ^ 0 ^ 0 (sử dụng tính chất A ^ A = 0)
= 2 (sử dụng tính chất A ^ 0 = A)

Lời giải tham khảo với C++:

#include 
using namespace std;

int findUnique(int arr[], int n) {
    int result = 0;

    for(int i=0; i n; i++) {
        result ^= arr[i];
    }

    return result;
}

int main() {
    int arr[] = {2, 3, 5, 4, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout  "Output = "  findUnique(arr, n);

    return 0;
}

Kết quả:

Output = 2

Trên đây là nội dung bài viết về các phép toán thao tác bit đi kèm các ví dụ sử dụng ngôn ngữ C++. Nếu bạn đọc có nhận xét hoặc thắc mắc có thể để lại bình luận phía cuối bài viết hoặc đặt câu hỏi tại nhóm Lập Trình Không Khó.

BÀI LIÊN QUAN
1