Bài 8.2: Bitset và các thao tác bit hiệu quả

Trong thế giới lập trình, đôi khi chúng ta cần lưu trữ và xử lý một lượng lớn các giá trị boolean (true/false). Nếu sử dụng các kiểu dữ liệu thông thường như bool hoặc int để biểu diễn trạng thái (0 hoặc 1), mỗi giá trị này sẽ chiếm ít nhất 1 byte bộ nhớ, thậm chí là 4 byte trên một số kiến trúc. Điều này có thể trở thành một vấn đề nghiêm trọng về bộ nhớ và hiệu suất khi chúng ta làm việc với hàng triệu hoặc hàng tỷ trạng thái.

May mắn thay, máy tính hoạt động ở cấp độ bit, nơi mà một trạng thái true/false thực sự chỉ cần một bit để biểu diễn! Đây chính là lúc các thao tác bit (bitwise operations) và cấu trúc dữ liệu chuyên dụng như bitset trong C++ phát huy sức mạnh, giúp chúng ta lưu trữ và xử lý dữ liệu cực kỳ hiệu quả ở cấp độ thấp nhất.

Trong bài viết này, chúng ta sẽ đi sâu vào bitset của C++ Standard Library – một công cụ mạnh mẽ cho phép chúng ta làm việc với các tập hợp bit có kích thước cố định một cách tối ưu, cùng với các thao tác bit cơ bản nhưng vô cùng hiệu quả.

bitset: Lợi ích của việc làm việc ở cấp độ bit

bitset là một template class trong C++ được thiết kế để lưu trữ một chuỗi bit có kích thước cố định tại thời điểm biên dịch. Thay vì sử dụng 1 byte hoặc hơn cho mỗi giá trị boolean, bitset đóng gói (pack) các bit lại với nhau, chỉ sử dụng đúng lượng bộ nhớ cần thiết (ví dụ: 1 byte cho 8 bit).

Tại sao lại sử dụng bitset?

  1. Tiết kiệm bộ nhớ: Đây là lợi ích rõ ràng nhất. Để lưu trữ N giá trị boolean, bạn chỉ cần khoảng N/8 byte bộ nhớ (cộng thêm một chút overhead nhỏ), thay vì N byte hoặc 4N byte.
  2. Hiệu suất cao: Các thao tác trên bitset thường được triển khai bằng các chỉ thị cấp thấp của CPU, cho phép xử lý đồng thời nhiều bit (ví dụ: 64 bit cùng lúc trên hệ thống 64-bit) chỉ với một lệnh duy nhất. Điều này nhanh hơn đáng kể so với việc lặp qua từng phần tử trong mảng bool thông thường.
  3. Các thao tác bit tiện lợi: bitset cung cấp giao diện trực quan cho các thao tác bit phổ biến như AND, OR, XOR, NOT, dịch bit (shift), đếm số bit 1, kiểm tra bit, v.v.

Lưu ý: bitset có kích thước cố định được chỉ định tại thời điểm biên dịch dưới dạng template parameter <N>. Nếu bạn cần một tập hợp bit có kích thước động, vector<bool> là một lựa chọn khác, mặc dù nó có thể không hiệu quả bằng bitset cho các thao tác bitwise tổng thể và có một số đặc thù riêng (ví dụ: vector<bool>::reference).

Khởi tạo và Truy cập bitset

Để sử dụng bitset, bạn cần include header <bitset>. Kích thước N phải là một hằng số nguyên dương.

#include <bitset>
#include <iostream>
#include <string>

int main() {
    // Khởi tạo một bitset có 8 bit (tất cả đều là 0 theo mặc định)
    bitset<8> b1; // b1: 00000000
    cout << "b1: " << b1 << endl;

    // Khởi tạo từ một số nguyên không dấu
    // Số 42 trong hệ nhị phân là 00101010
    bitset<8> b2(42); // b2: 00101010
    cout << "b2 (from 42): " << b2 << endl;

    // Khởi tạo từ một chuỗi string ('0' hoặc '1')
    // Ký tự đầu tiên của string tương ứng với bit có chỉ số cao nhất
    bitset<10> b3(string("1011011001")); // b3: 1011011001
    cout << "b3 (from string): " << b3 << endl;

    // Truy cập và kiểm tra từng bit
    // Lưu ý: chỉ số bit bắt đầu từ 0 ở bên phải (bit LSB - Least Significant Bit)
    cout << "Bit thu 0 cua b2: " << b2[0] << endl; // b2[0] la bit ngoai cung ben phai
    cout << "Bit thu 5 cua b2: " << b2[5] << endl; // b2[5] la bit 1 trong 00101010

    // Sử dụng .test() để kiểm tra bit (trả về bool)
    cout << "Kiem tra bit thu 3 cua b2: " << b2.test(3) << endl; // Bit thu 3 la 0
    cout << "Kiem tra bit thu 5 cua b2: " << b2.test(5) << endl; // Bit thu 5 la 1

    return 0;
}

Giải thích:

  • bitset<N> khai báo một bitset có N bit. <8> và <10> là kích thước.
  • Khởi tạo mặc định làm cho tất cả các bit bằng 0.
  • Khởi tạo từ số nguyên không dấu sẽ biểu diễn số đó dưới dạng nhị phân trong bitset.
  • Khởi tạo từ string cho phép bạn thiết lập các bit theo chuỗi '0' và '1' cung cấp. Ký tự đầu tiên của string là bit có trọng số cao nhất (most significant bit - MSB).
  • b[i] cho phép truy cập bit thứ i. Bit thứ 0 là bit ít quan trọng nhất (bên phải cùng).
  • b.test(i) là cách an toàn và rõ ràng hơn để kiểm tra trạng thái boolean của bit thứ i.

Các Thao Tác Thay Đổi Trạng Thái Bit

bitset cung cấp các phương thức để thay đổi trạng thái của các bit một cách dễ dàng.

#include <bitset>
#include <iostream>

int main() {
    bitset<8> b(42); // b: 00101010
    cout << "Ban dau: " << b << endl;

    // Dat bit thu 0 ve 1 (.set())
    b.set(0); // b: 00101011
    cout << "Dat bit 0: " << b << endl;

    // Dat bit thu 3 ve 1 (.set(index, value))
    b.set(3, true); // b: 00101011 (da la 1) -> 00101011
    cout << "Dat bit 3 ve true: " << b << endl;

    // Dat bit thu 4 ve 0 (.set(index, value))
    b.set(4, false); // b: 00101011 -> 00100011
    cout << "Dat bit 4 ve false: " << b << endl;

    // Dat bit thu 5 ve 0 (.reset())
    b.reset(5); // b: 00100011 -> 00000011
    cout << "Reset bit 5: " << b << endl;

    // Dao nguoc trang thai bit thu 1 (.flip())
    b.flip(1); // b: 00000011 -> 00000001
    cout << "Flip bit 1: " << b << endl;

    // Dao nguoc tat ca cac bit (.flip())
    b.flip(); // b: 00000001 -> 11111110
    cout << "Flip tat ca: " << b << endl;

    // Dat tat ca cac bit ve 1 (.set())
    b.set(); // b: 11111110 -> 11111111
    cout << "Set tat ca: " << b << endl;

    // Dat tat ca cac bit ve 0 (.reset())
    b.reset(); // b: 11111111 -> 00000000
    cout << "Reset tat ca: " << b << endl;

    return 0;
}

Giải thích:

  • b.set(i): Đặt bit thứ i thành 1.
  • b.set(i, value): Đặt bit thứ i thành value (true hoặc false).
  • b.reset(i): Đặt bit thứ i thành 0.
  • b.flip(i): Đảo ngược trạng thái của bit thứ i (0 thành 1, 1 thành 0).
  • b.set(): Đặt tất cả các bit thành 1.
  • b.reset(): Đặt tất cả các bit thành 0.
  • b.flip(): Đảo ngược trạng thái của tất cả các bit.

Các Thao Tác Bitwise Logic (AND, OR, XOR, NOT)

Sức mạnh thực sự của bitset nằm ở khả năng thực hiện các thao tác logic trên toàn bộ tập hợp bit một cách hiệu quả, tương tự như các phép toán bitwise trên số nguyên. Các toán tử & (AND), | (OR), ^ (XOR) và ~ (NOT) được nạp chồng (overload) cho bitset.

#include <bitset>
#include <iostream>

int main() {
    bitset<8> b1(string("10101100")); // b1: 10101100
    bitset<8> b2(string("01101010")); // b2: 01101010

    cout << "b1: " << b1 << endl;
    cout << "b2: " << b2 << endl;

    // AND (&&)
    // b1: 10101100
    // b2: 01101010
    // & : 00101000
    bitset<8> b_and = b1 & b2;
    cout << "b1 & b2: " << b_and << endl;

    // OR (||)
    // b1: 10101100
    // b2: 01101010
    // | : 11101110
    bitset<8> b_or = b1 | b2;
    cout << "b1 | b2: " << b_or << endl;

    // XOR (^)
    // b1: 10101100
    // b2: 01101010
    // ^ : 11000110
    bitset<8> b_xor = b1 ^ b2;
    cout << "b1 ^ b2: " << b_xor << endl;

    // NOT (~)
    // b1: 10101100
    // ~b1: 01010011 (dao nguoc tat ca cac bit)
    bitset<8> b_not_b1 = ~b1;
    cout << "~b1: " << b_not_b1 << endl;

    return 0;
}

Giải thích:

Các toán tử bitwise (&, |, ^) hoạt động trên từng cặp bit tương ứng của hai bitset cùng kích thước. Toán tử ~ (NOT) đảo ngược trạng thái của mỗi bit trong bitset. Các phép toán này thường được thực hiện rất nhanh ở cấp độ phần cứng.

Dịch Bit (Shift Operations)

Các thao tác dịch bit (<< - dịch trái, >> - dịch phải) cũng được hỗ trợ.

#include <bitset>
#include <iostream>

int main() {
    bitset<8> b(string("10110010")); // b: 10110010
    cout << "Ban dau: " << b << endl;

    // Dich trai 2 vi tri (them 0 vao ben phai)
    // 10110010 << 2 -> 11001000
    bitset<8> b_left_shift = b << 2;
    cout << "Dich trai 2: " << b_left_shift << endl;

    // Dich phai 3 vi tri (them 0 vao ben trai)
    // 10110010 >> 3 -> 00010110
    bitset<8> b_right_shift = b >> 3;
    cout << "Dich phai 3: " << b_right_shift << endl;

    // Cac phep gan ket hop dich
    bitset<8> b_mutable(string("00011100"));
    b_mutable <<= 1; // 00011100 <<= 1 -> 00111000
    cout << "Dich trai va gan: " << b_mutable << endl;

    b_mutable >>= 2; // 00111000 >>= 2 -> 00001110
    cout << "Dich phai va gan: " << b_mutable << endl;

    return 0;
}

Giải thích:

  • b << N: Dịch tất cả các bit sang trái N vị trí. N bit 0 sẽ được thêm vào bên phải.
  • b >> N: Dịch tất cả các bit sang phải N vị trí. N bit 0 sẽ được thêm vào bên trái (đây là logical shift, không phải arithmetic shift).
  • Các toán tử gán kết hợp <<= và >>= thực hiện phép dịch và gán kết quả trở lại bitset ban đầu.

Đếm Bit và Kiểm Tra Trạng Thái Tổng Quát

bitset cung cấp các phương thức tiện lợi để kiểm tra trạng thái tổng quát hoặc đếm số lượng bit 1.

#include <bitset>
#include <iostream>

int main() {
    bitset<10> b(string("1011011001")); // b: 1011011001
    cout << "Bitset: " << b << endl;

    // Kich thuoc cua bitset
    cout << "Kich thuoc (so bit): " << b.size() << endl; // Output: 10

    // Dem so luong bit 1 (set bits)
    cout << "So luong bit 1: " << b.count() << endl; // b co 6 bit 1

    // Kiem tra xem co bat ky bit nao la 1 khong
    cout << "Co bit nao la 1 khong? " << b.any() << endl; // Output: 1 (true)

    // Kiem tra xem tat ca cac bit co la 0 khong
    cout << "Tat ca co la 0 khong? " << b.none() << endl; // Output: 0 (false)

    // Kiem tra xem tat ca cac bit co la 1 khong
    cout << "Tat ca co la 1 khong? " << b.all() << endl; // Output: 0 (false)

    bitset<5> all_zero; // 00000
    bitset<5> all_one;
    all_one.set(); // 11111

    cout << "\nAll zero: " << all_zero << endl;
    cout << "Co bit nao la 1 khong? " << all_zero.any() << endl; // Output: 0 (false)
    cout << "Tat ca co la 0 khong? " << all_zero.none() << endl; // Output: 1 (true)
    cout << "Tat ca co la 1 khong? " << all_zero.all() << endl; // Output: 0 (false)

    cout << "\nAll one: " << all_one << endl;
    cout << "Co bit nao la 1 khong? " << all_one.any() << endl; // Output: 1 (true)
    cout << "Tat ca co la 0 khong? " << all_one.none() << endl; // Output: 0 (false)
    cout << "Tat ca co la 1 khong? " << all_one.all() << endl; // Output: 1 (true)

    return 0;
}

Giải thích:

  • b.size(): Trả về tổng số bit trong bitset (hằng số N).
  • b.count(): Trả về số lượng bit có giá trị 1.
  • b.any(): Trả về true nếu có ít nhất một bit là 1, ngược lại trả về false.
  • b.none(): Trả về true nếu tất cả các bit là 0, ngược lại trả về false. Equivalent to !b.any().
  • b.all(): Trả về true nếu tất cả các bit là 1, ngược lại trả về false. Equivalent to b.count() == b.size().

Chuyển Đổi Giữa bitset và các Kiểu Dữ Liệu Khác

Bạn có thể chuyển đổi bitset sang chuỗi string hoặc sang các kiểu số nguyên không dấu (nếu bitset đủ nhỏ).

#include <bitset>
#include <iostream>
#include <string>

int main() {
    bitset<10> b(string("1011011001")); // b: 1011011001
    cout << "Bitset: " << b << endl;

    // Chuyen doi sang string
    string s = b.to_string();
    cout << "Chuyen doi sang string: " << s << endl; // Output: 1011011001

    // Chuyen doi sang unsigned long (neu bitset <= sizeof(unsigned long) * 8)
    // 1011011001 (base 2) = 512 + 128 + 64 + 16 + 8 + 1 = 729 (base 10)
    unsigned long ul = b.to_ulong();
    cout << "Chuyen doi sang unsigned long: " << ul << endl; // Output: 729

    // Chuyen doi sang unsigned long long (neu bitset <= sizeof(unsigned long long) * 8)
    unsigned long long ull = b.to_ullong();
    cout << "Chuyen doi sang unsigned long long: " << ull << endl; // Output: 729

    // Can than voi kich thuoc lon hon
    // bitset<100> large_b;
    // large_b.set(99); // Bit cao nhat
    // large_b.set(0);  // Bit thap nhat
    // // ul = large_b.to_ulong(); // LOI: Bitset qua lon so voi unsigned long
    // ull = large_b.to_ullong(); // LOI: Bitset qua lon so voi unsigned long long

    return 0;
}

Giải thích:

  • b.to_string(): Chuyển đổi bitset thành một chuỗi các ký tự '0' và '1'. Bit có chỉ số cao nhất tương ứng với ký tự đầu tiên của chuỗi.
  • b.to_ulong(): Chuyển đổi bitset thành giá trị của một số nguyên không dấu kiểu unsigned long.
  • b.to_ullong(): Chuyển đổi bitset thành giá trị của một số nguyên không dấu kiểu unsigned long long.

Quan trọng: Các phương thức to_ulong() và to_ullong() sẽ ném ra exception overflow_error nếu giá trị của bitset vượt quá khả năng biểu diễn của kiểu đích (unsigned long hoặc unsigned long long). Hãy chắc chắn rằng kích thước của bitset (N) không lớn hơn số bit của kiểu đích (thường là 32 hoặc 64).

Ứng Dụng của bitset và Thao Tác Bit

bitset và các thao tác bit hiệu quả được sử dụng rộng rãi trong nhiều lĩnh vực:

  • Các thuật toán số học và logic: Biểu diễn và thao tác trên các tập hợp bit, thường dùng trong mật mã, nén dữ liệu.
  • Các bài toán trên đồ thị: Biểu diễn ma trận kề (adjacency matrix) của đồ thị thưa (sparse graph) để tiết kiệm bộ nhớ, hoặc dùng để theo dõi trạng thái duyệt.
  • Các thuật toán tìm kiếm và lọc: Ví dụ, Sàng Eratosthenes (Sieve of Eratosthenes) để tìm số nguyên tố dưới một ngưỡng N có thể được tối ưu đáng kể về bộ nhớ bằng cách sử dụng bitset<N+1> để đánh dấu các số đã sàng.
  • Trạng thái cờ (flags): Lưu trữ nhiều cờ boolean trong một biến duy nhất (bitmask) thay vì nhiều biến bool.
  • Tối ưu bộ nhớ trong các cấu trúc dữ liệu: Sử dụng bitset để biểu diễn các mảng boolean lớn một cách hiệu quả.

Bài tập ví dụ:

Cặp hợp lệ

Với công việc là nhân viên quản lý nhà hàng, FullHouse Dev được giao nhiệm vụ kiểm tra các cặp khách hàng vào nhà hàng Ý nổi tiếng. Theo quy định đặc biệt của nhà hàng, khách chỉ được vào theo cặp và tổng tài sản của cặp đó phải là lũy thừa của 3. FullHouse Dev cần giúp nhà hàng tính toán số lượng cặp khách hàng hợp lệ có thể được phép vào nhà hàng.

Bài toán

Cho một nhóm người với tài sản của từng người. Một cặp người với tài sản \(a\) và \(b\) được coi là hợp lệ nếu \(a + b = 3^k\) với \(k\) là một số nguyên dương. Nhiệm vụ của FullHouse Dev là tìm ra số lượng cặp hợp lệ có thể được tạo ra từ nhóm người này.

INPUT FORMAT:
  • Dòng đầu tiên chứa số nguyên \(N\) - số lượng người.
  • Dòng thứ hai chứa một mảng \(wealth\) biểu thị tài sản của từng người.
OUTPUT FORMAT:
  • In ra một số nguyên duy nhất biểu thị số lượng cặp hợp lệ.
Ràng buộc:
  • \(1 \leq N \leq 10^5\)
  • \(1 \leq wealth[i] \leq 10^9\)
Ví dụ
INPUT
4
1 5 2 4
OUTPUT
2
Giải thích
  • Với \(N = 4\) và mảng tài sản \([1, 5, 2, 4]\), có hai cặp hợp lệ:
    • Cặp người thứ nhất và thứ ba có tổng tài sản là \(1 + 2 = 3\) (là lũy thừa của 3)
    • Cặp người thứ hai và thứ tư có tổng tài sản là \(5 + 4 = 9\) (là lũy thừa của 3)
Lưu ý:
  • Một người có thể thuộc nhiều cặp hợp lệ khác nhau
  • Cặp người X và Y được coi là giống với cặp người Y và X Tuyệt vời! Đây là hướng giải ngắn gọn cho bài toán "Cặp hợp lệ" bằng C++ mà không cung cấp code hoàn chỉnh:

  1. Ý tưởng chính: Bài toán yêu cầu tìm cặp (a, b) sao cho a + b là một lũy thừa dương của 3. Có rất ít các lũy thừa của 3 mà tổng tài sản của hai người có thể đạt được (tổng tối đa khoảng 2 * 10^9, các lũy thừa của 3 nhanh chóng vượt quá giá trị này). Ta có thể tiền tính các lũy thừa của 3 này. Sau đó, với mỗi người có tài sản w, ta tìm những người khác có tài sản target - w, trong đó target là một trong các lũy thừa của 3.

  2. Đếm tần suất: Để tìm nhanh những người có tài sản target - w và biết số lượng của họ, hãy sử dụng một cấu trúc dữ liệu như unordered_map (hoặc map) để lưu trữ tần suất xuất hiện của mỗi giá trị tài sản trong mảng đầu vào. Khóa của map là giá trị tài sản, và giá trị là số lần xuất hiện.

  3. Lập danh sách các mục tiêu (powers of 3): Tạo một danh sách (ví dụ: vector) chứa các lũy thừa của 3 (từ 3^1 trở đi) mà nhỏ hơn hoặc bằng tổng tài sản tối đa có thể có (khoảng 2 * 10^9).

  4. Đếm cặp:

    • Duyệt qua map tần suất. Với mỗi cặp (tài sản A, số lượng A) trong map:
    • Duyệt qua danh sách các lũy thừa của 3 (các mục tiêu T).
    • Tính giá trị cần tìm tài sản B = T - tài sản A.
    • Nếu tài sản B tồn tại trong map tần suất:
      • Lấy số lượng tài sản B (số lượng B).
      • Trường hợp 1: tài sản A == tài sản B. Đây là trường hợp cặp có hai người cùng tài sản. Số lượng cặp tạo được là (số lượng A * (số lượng A - 1)) / 2. Cộng vào tổng số cặp. Lưu ý: Chỉ xử lý trường hợp này một lần khi tài sản A == tài sản B.
      • Trường hợp 2: tài sản A < tài sản B. Đây là trường hợp cặp có hai người tài sản khác nhau. Số lượng cặp tạo được là số lượng A * số lượng B. Cộng vào tổng số cặp. Lưu ý: Chỉ xử lý khi tài sản A < tài sản B để tránh đếm hai lần cặp (A, B) và (B, A).
      • Trường hợp 3: tài sản A > tài sản B. Bỏ qua, cặp (B, A) sẽ được đếm khi ta xử lý tài sản B trong vòng lặp ngoài (vì tài sản B < tài sản A).

  5. Kiểu dữ liệu: Sử dụng kiểu long long cho tài sản, tổng tài sản và biến đếm tổng số cặp để tránh tràn số, vì tài sản có thể lên tới 10^9 và số cặp có thể rất lớn.

  6. Kết quả: In ra tổng số cặp đã đếm được.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.