# Nhập Môn bit

[toc]
## Khái niệm về bit
Bit (viết tắt của "binary digit") là đơn vị thông tin nhỏ nhất trong máy tính, có giá trị 0 hoặc 1, dùng để biểu diễn dữ liệu trong hệ nhị phân. Nói cách khác bit của một số nguyên là cách biểu diễn của số đó dưới dạng nhị phân

12 = 1100
13 = 1101
25 = 11001

Cách để biến đổi từ số nguyên từ hệ thập phân thành hệ nhị phân được mô ta theo hình bên dưới


Dưới đây là cách biến đổi từ hệ nhị phân sang thập phân


## Các toán tử với bit (bitwise operators)

### Phép AND
- **Định nghĩa**: là phép toán logic hoạt động trên từng bit của hai số nguyên. Kết quả tại mỗi vị trí bit sẽ là 1 nếu cả hai bit tương ứng của hai số đầu vào đều là 1, ngược lại sẽ là 0.
- **Cú pháp**:

result = a & b;

- **Ứng dụng**: Kiểm tra tính chẵn lẻ của 1 số, bật tắt 1 bit cụ thể,...
- **Ví dụ**:
- *Problem*: Viết chương trình kiểm tra và hiển thị kết quả phép toán $AND$ giữa hai số nguyên $𝐴$ và $𝐵$.
- *Solution*:

    #include <iostream>
    using namespace std;

    int main() {
        // Nhập hai số nguyên
        int A, B;
        cout << "Nhap so nguyen A: ";
        cin >> A;
        cout << "Nhap so nguyen B: ";
        cin >> B;

        // Thực hiện phép AND
        int result = A & B;

        // In kết quả
        cout << "Ket qua cua " << A << " & " << B << " la: " << result << endl;

        return 0;
    }

### Phép OR
- **Định nghĩa**: là một phép toán logic được thực hiện trên từng bit của hai số nguyên. Kết quả tại mỗi vị trí bit sẽ là:
- 1 nếu ít nhất một bit trong hai bit đầu vào là 1.
- 0 nếu cả hai bit đầu vào đều là 0.
- **Cú pháp**:

result = a | b;

- **Ứng dụng**: Thiết lập bit, bật tắt 1 số bit cụ thể, tối ưu hóa bộ nhớ trong việc tính toán các phép tính giữa các số lớn,...
- **Ví dụ**:
- *Problem*: Viết chương trình kiểm tra và hiển thị kết quả phép toán $OR$ giữa hai số nguyên $𝐴$ và $𝐵$.
- *Solution*:

    #include <iostream>
    using namespace std;

    int main() {
        // Nhập hai số nguyên
        int A, B;
        cout << "Nhap so nguyen A: ";
        cin >> A;
        cout << "Nhap so nguyen B: ";
        cin >> B;

        // Thực hiện phép OR
        int result = A | B;

        // In kết quả
        cout << "Ket qua cua " << A << " | " << B << " la: " << result << endl;

        return 0;
    }

### Phép XOR
- **Định nghĩa**: là một phép toán trong lập trình hoạt động trực tiếp trên các bit của số nhị phân. Quy tắc của phép XOR (Exclusive OR) như sau:
- **0 ^ 0 = 0**
- **0 ^ 1 = 1**
- **1 ^ 0 = 1**
- **1 ^ 1 = 0**
- **Cú pháp**:

result = a ^ b;

- **Ứng dụng**: Tìm giá trị duy nhất trong một tập hợp, so sánh các số, tạo các số ngẫu nhiên,...
- **Ví dụ**:
- *Problem*: Viết chương trình kiểm tra và hiển thị kết quả phép toán $XOR$ giữa hai số nguyên $𝐴$ và $𝐵$.
- *Solution*:

    #include <iostream>
    using namespace std;

    int main() {
        // Nhập hai số nguyên
        int A, B;
        cout << "Nhap so nguyen A: ";
        cin >> A;
        cout << "Nhap so nguyen B: ";
        cin >> B;

        // Thực hiện phép XOR
        int result = A ^ B;

        // In kết quả
        cout << "Ket qua cua " << A << " ^ " << B << " la: " << result << endl;

        return 0;
    }

### Dịch chuyển bit

- **Định nghĩa:** dịch bit là cách đây các bit trong một số nguyên sang trái hoặc sang phải ví dụ
- $a$ >> $b$ : các bit của $a$ được dịch sang phải $b$ bit
- $a$ << $b$ : các bit của $a$ được dịch sang trái $b$ bit
- **Ví dụ**:
- *Problem*: Viết chương trình kiểm tra và hiển thị kết quả phép toán dịch $B$ bit của $A$ sang trái và sang phải
- *Solution*:

    #include <bits/stdc++.h>
    using namespace std;

    int main() 
    {
        int a = 0,b = 0;
        cin >> a >> b;
        cout << (a >> b) << " " << (a << b);
        return 0;
    }

---
## Cấu trúc dữ liệu bitset
- Trong C++, $bitset$ là một cấu trúc dữ liệu có sẵn trong thư viện <$bitset$> giúp lưu trữ và thao tác với dãy bit **(bit array)**. Nó là một kiểu dữ liệu rất hữu ích khi bạn cần làm việc với các giá trị nhị phân hoặc các thao tác bitwise (bitwise operations).
- **Đặc điểm**:
- $bitset$ là một kiểu dữ liệu cố định kích thước (số lượng bit được xác định khi khai báo).
- Mỗi phần tử của $bitset$ là một bit (0 hoặc 1).
- Cung cấp các phương thức tiện ích để thao tác với các *bit*, chẳng hạn như thay đổi giá trị *bit*, kiểm tra *bit*, hoặc chuyển đổi giữa các kiểu dữ liệu khác.
- **Cách sử dụng**:
- Khai báo $bitset$:

    #include <bitset>
    #include <iostream>
    using namespace std;

    int main() {
        // Khai báo bitset với 8 bit, tất cả các bit đều là 0
        bitset<8> b1;
        cout << "b1: " << b1 << endl;  // Output: 00000000

        // Khai báo bitset và khởi tạo giá trị bằng một chuỗi nhị phân
        bitset<8> b2("10101010");
        cout << "b2: " << b2 << endl;  // Output: 10101010

        return 0;
    }

- Các phương thức của $bitset$:
- **size()**: Trả về số lượng bit trong bitset.
- **count()**: Trả về số lượng bit có giá trị là 1 trong bitset.
- **set()**: Đặt tất cả các bit trong bitset thành 1, hoặc chỉ một bit cụ thể thành 1.
- **reset()**: Đặt tất cả các bit trong bitset thành 0, hoặc chỉ một bit cụ thể thành 0.
- **flip()**: Lật tất cả các bit trong bitset, hoặc lật một bit cụ thể.
- **test()**: Kiểm tra giá trị của một bit tại vị trí chỉ định (trả về true nếu bit đó là 1, false nếu là 0).
- **to_string()**: Chuyển đổi bitset thành một chuỗi nhị phân dạng string.
- **to_ulong()**: Chuyển đổi bitset thành kiểu unsigned long
- Ví dụ:

    #include <bitset>
    #include <iostream>
    using namespace std;

    int main() {
        bitset<8> b1("10101010");

        // Kiểm tra số lượng bit là 1
        cout << "Number of 1s in b1: " << b1.count() << endl;  // Output: 4

        // Đặt tất cả các bit thành 1
        b1.set();
        cout << "After set: " << b1 << endl;  // Output: 11111111

        // Đặt bit ở vị trí 3 thành 0
        b1.reset(3);
        cout << "After reset bit 3: " << b1 << endl;  // Output: 11110111

        // Lật tất cả các bit
        b1.flip();
        cout << "After flip: " << b1 << endl;  // Output: 00001000

        // Chuyển đổi bitset thành string
        string bitString = b1.to_string();
        cout << "Bitset as string: " << bitString << endl;  // Output: 00001000

        // Chuyển đổi bitset thành unsigned long
        unsigned long decimal = b1.to_ulong();
        cout << "Bitset as unsigned long: " << decimal << endl;  // Output: 8

        return 0;
    }

- **Ứng dụng**:
- *Xử lý dữ liệu nhị phân*: bitset rất hữu ích khi bạn làm việc với dữ liệu nhị phân và cần các phép toán bitwise.
- *Khai báo và thao tác với cờ (flags)*: Khi bạn cần theo dõi một số trạng thái trong chương trình, ví dụ như trong các chương trình quản lý cờ (flag management), bitset có thể giúp lưu trữ và thao tác với các cờ dễ dàng.
- *Tối ưu bộ nhớ*: Khi bạn cần lưu trữ nhiều giá trị boolean (true/false), bitset giúp tiết kiệm bộ nhớ so với việc sử dụng mảng boolean thông thường, vì mỗi phần tử trong bitset chỉ chiếm một bit thay vì một byte.

---
## Kỹ thuật Bit-mask
- **Khái niệm:** Bitmask là một kỹ thuật sử dụng các số nhị phân (bit) để đại diện cho các trạng thái hoặc tùy chọn khác nhau. Mỗi bit trong bitmask có thể bật (1) hoặc tắt (0), giúp bạn lưu trữ nhiều trạng thái trong một số duy nhất và thực hiện các thao tác nhanh gọn như kiểm tra, đặt, hoặc xóa trạng thái bằng các phép toán nhị phân (AND, OR, XOR, NOT).

- Từ khái niệm trên ta có thể ứng dụng Bitmask vô cách sinh tập hay cách chọn của một tấp số
Cách hoạt động: Ta biết với mỗi $n$ phần tử luôn tồn tại $2^n$ cách chọn khác nhau. Từ đó ta có thể áp dụng vào kỹ thuật trên bằng cách với mỗi cấu hình mask ta sẽ kiểm tra những bit có giá trị 1 tượng trưng đồng nghĩa với đó là vị trí được chọn.
> code dưới đây là cách minh họa của ý tưởng trên

#include <iostream>
#include <vector>

using namespace std;

void generateSubsets(const vector<int>& set) {
    int n = set.size();
    int totalSubsets = 1 << n; // 2^n, tổng số tập con

    cout << "Các tập con của tập hợp: " << endl;

    for (int mask = 0; mask < totalSubsets; ++mask) {
        cout << "{ ";
        for (int i = 0; i < n; ++i) {
            // Kiểm tra nếu bit thứ i của mask là 1
            if (mask & (1 << i)) {
                cout << set[i] << " ";
            }
        }
        cout << "}" << endl;
    }
}

int main() {
    vector<int> mySet = {1, 2, 3}; // Tập hợp ví dụ
    generateSubsets(mySet);
    return 0;
}