Khóa học CTDL và GT

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ư std::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 std::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ả.

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

std::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, std::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 std::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 std::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: std::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 ý: std::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, std::vector<bool> là một lựa chọn khác, mặc dù nó có thể không hiệu quả bằng std::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 std::bitset

Để sử dụng std::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)
    std::bitset<8> b1; // b1: 00000000
    std::cout << "b1: " << b1 << std::endl;

    // Khởi tạo từ một số nguyên không dấu
    // Số 42 trong hệ nhị phân là 00101010
    std::bitset<8> b2(42); // b2: 00101010
    std::cout << "b2 (from 42): " << b2 << std::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
    std::bitset<10> b3(std::string("1011011001")); // b3: 1011011001
    std::cout << "b3 (from string): " << b3 << std::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)
    std::cout << "Bit thu 0 cua b2: " << b2[0] << std::endl; // b2[0] la bit ngoai cung ben phai
    std::cout << "Bit thu 5 cua b2: " << b2[5] << std::endl; // b2[5] la bit 1 trong 00101010

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

    return 0;
}

Giải thích:

• std::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

std::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() {
    std::bitset<8> b(42); // b: 00101010
    std::cout << "Ban dau: " << b << std::endl;

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

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

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

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

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

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

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

    // Dat tat ca cac bit ve 0 (.reset())
    b.reset(); // b: 11111111 -> 00000000
    std::cout << "Reset tat ca: " << b << std::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 std::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() {
    std::bitset<8> b1(std::string("10101100")); // b1: 10101100
    std::bitset<8> b2(std::string("01101010")); // b2: 01101010

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

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

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

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

    // NOT (~)
    // b1: 10101100
    // ~b1: 01010011 (dao nguoc tat ca cac bit)
    std::bitset<8> b_not_b1 = ~b1;
    std::cout << "~b1: " << b_not_b1 << std::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() {
    std::bitset<8> b(std::string("10110010")); // b: 10110010
    std::cout << "Ban dau: " << b << std::endl;

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

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

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

    b_mutable >>= 2; // 00111000 >>= 2 -> 00001110
    std::cout << "Dich phai va gan: " << b_mutable << std::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

std::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() {
    std::bitset<10> b(std::string("1011011001")); // b: 1011011001
    std::cout << "Bitset: " << b << std::endl;

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

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

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

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

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

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

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

    std::cout << "\nAll one: " << all_one << std::endl;
    std::cout << "Co bit nao la 1 khong? " << all_one.any() << std::endl; // Output: 1 (true)
    std::cout << "Tat ca co la 0 khong? " << all_one.none() << std::endl; // Output: 0 (false)
    std::cout << "Tat ca co la 1 khong? " << all_one.all() << std::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 std::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() {
    std::bitset<10> b(std::string("1011011001")); // b: 1011011001
    std::cout << "Bitset: " << b << std::endl;

    // Chuyen doi sang string
    std::string s = b.to_string();
    std::cout << "Chuyen doi sang string: " << s << std::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();
    std::cout << "Chuyen doi sang unsigned long: " << ul << std::endl; // Output: 729

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

    // Can than voi kich thuoc lon hon
    // std::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 std::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 std::bitset và Thao Tác Bit

std::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 std::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ư std::unordered_map (hoặc std::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ụ: std::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