# Xử lý bit

*Bài giảng về “Xử lý bit” của thầy Thuận, trại hè Thái Nguyên 2023*

# Các kiểu dữ liệu cơ bản

`bool`

`char`

`short`

…

n byte → min = $-2^{8n - 1}$, max = $2^{8n - 1} - 1$

`unsigned` - không có số âm → max = $2^{8n} - 1$

# Thao tác bit

Số nhị phân: $(a_k a_{k - 1} \dots a_0)_2 = a_k \cdot 2^k + a_{k-1} \cdot 2^{k - 1} + \dots + a_0 \cdot 2^0$

Các số âm được biểu diễn dưới dạng phần bù của hai:

- Bắt đầu với số dương tương đương
- Đảo bit 0 → 1, 1→ 0
- Cộng 1 vào số vừa đảo ngược.

## Toán tử theo bit (bitwise)

- Toán tử AND:
- 1 & 1 → 1
- còn lại → 0
- Toán tử OR:
- 0 | 0 → 0
- còn lại → 1 (có một trong hai số là 1)
- Toán tử XOR:
- Hai bit khác nhau → 1
- Hai bit giống nhau → 0
- Toán tử NOT: lật bit 0 → 1, 1 → 0

## Toán tử dịch chuyển

- `>>`: Dịch sang phải bằng cách xóa một vài chữ số nhị phân cuối cùng của số đó.
- Dịch một bước tương ứng với phép chia cho 2.
- $5 >> 2 = 101_2 >> 2 = 1_2 = 1$, giống với $5 / 4 = 1$.
- Dùng >> nhanh hơn chia bình thường.
- `<<`: Dịch sáng trái bằng cách nối thêm các số 0.
- Tương tự, phép dịch trái tương ứng với phép nhân với 2.
- $5 << 3 = 101_2 << 3 = 101000_2 = 40$, giống với $5 \cdot 2^3 = 40$
- Đối với số nguyên có độ dài cố định, phép dịch trái là loại bỏ các chữ số trái nhất và dịch trái quá nhiều kết quả nhận được sẽ là 0.

## Thay đổi một bit

- `1 << x` là số chỉ có bit thứ $x$ được bật → `~(1 << x)` là số có tất cả các bit đều bật trừ bit $x$.
- `n | (1 << x)` là bật bit thứ $x$ của số $n$
- `n ^ (1 << x)`lật bit thứ $x$ của số $n$
- `n & ~(1 << x)` tắt bit thứ $x$ của số $n$

## Kiểm tra một bit có được bật hay không

- Dịch x vị trí sang bên phải và thực hiện phép & với 1.
- `(num >> x) & 1`
- `num & (1 << x)` ( dịch 1 sang trái x lần)

## Kiểm tra một số có phải lũy thừa của 2 hay không

- Lũy thừa của 2 có duy nhất một bit được bật → số liền trước có tất cả các bit sau nó được bật.
- → Phép AND của một số với số liền trước đó bằng 0 khi và chỉ khi số đó là lũy thừa của 2.
- `return n && !(n & (n - 1))`
- Chú ý `n > 0`

## Tắt bit được bật bên phải nhất

- Biểu thức n - 1 lật tất cả các bit sau bit được đặt ngoài cùng bên phải của n, bao gồm cả bit được đặt ngoài cùng bên phải → sử dụng phép AND
- `n & (n - 1)`

## Thuật toán Brian Kernighan

- Đếm số bit được bật.
- Ý tưởng: tắt bit ngoài cùng bên phải liên tục cho đến khi số đó về 0.

int cnt = 0;
while(n){
    n = n & (n - 1);
    ++cnt;
}

## Các thủ thuật khác

- `n & (n + 1)` tắt tất cả các bit 1 cuối
- `n | (n + 1)` bật bit 0 cuối cùng
- `n & -n` trích bit 1 cuối cùng
- Tham khảo thêm trong cuốn sách Hacker’s Delight

# Biểu diễn tập hợp bằng Bitmask

## Biểu diễn tập hợp

- Cho một số lượng nhỏ (< 30) phần tử
- Gán nhãn bới các số nguyên 0, 1, …, n - 1
- Biểu diễn tập hợp bởi một số nguyên 32 - bit
- Phần tử thứ i trong tập được biểu diễn bằng số nguyên x nếu bit thứ i của x là 1.
- Tập rỗng: 0
- Tập có một phần tử: `1 << i`
- Tập vũ trụ (chứa tất cả các phần tử) : `(1 << n) - 1`
- Hợp hai tập: `x | y`
- Giao hai tập: `x & y`
- Phần bù của một tập: `~x & ((1 << n) - 1)`
- Kiểm tra một phần tử xuất hiện trong tập: `x & (1 << i)`
- Biểu diễn đỡ tốn khá nhiều bộ nhớ
- Tất cả các tập con của tập n phần tử có thể biểu diễn bởi các số từ 0 đến $2^n - 1$
- Có thể lặp qua các tập con nhanh chóng

# Bitset trong C++

- Trong STL
- Về bản chất, bitset giống như một mảng/vector kiểu logic, gồm các phần tử chỉ mang giá trị 0/1, được cài đặt tối ưu để mỗi phần tử chỉ chiếm 1 bit.
- Các thao tác trên bitset sẽ nhanh hơn trên mảng/vector tới 64 lần, và không gian lưu trữ cũng sẽ nhỏ hơn rất nhiều.

## Khai báo bitset

#include <bitset>

using namespace std;

bitset<size> {name}(initialization);

- Không khới tạo, bitset sẽ mặc định bằng 0.
- Khới tạo bằng số nguyên hệ thập phân: bitset được khởi tạo bằng biểu diễn nhị phân của số truyền vào
- Khởi tạo bằng xâu nhị phân

## Truy cập các bit của bitset

- Phần tử được đánh số từ phải qua trái (giống số nhị phân)
- Truy cập giống mảng

## Một số hàm và toán tử của bitset

- `set(), reset(), flip(), count(), size(), any(), none(), to_string(), to_ulong(), to_ullong()`
- Các toán tử giống như thao tác bit: &, |, !, ≤, ≥, &=, |=, ^=, ~

Link bài tập: [https://codeforces.com/group/5W0GHUX15v/contest/452431](https://codeforces.com/group/5W0GHUX15v/contest/452431)

[https://codeforces.com/blog/entry/94470](https://codeforces.com/blog/entry/94470)