Thuật toán xử lý Bit (Bit Manipulation)
1. Giới thiệu
Xử lý bit là kỹ thuật thao tác trực tiếp với các bit trong biểu diễn nhị phân của dữ liệu. Các thao tác bit thường nhanh và tiết kiệm bộ nhớ hơn các phép toán thông thường.
2. Các phép toán cơ bản
- AND (&)
- OR (|)
- XOR (^)
- NOT (~)
- Dịch trái (<<)
- Dịch phải (>>)
- Dịch phải không dấu (>>>)
3. Các kỹ thuật phổ biến
3.1. Kiểm tra bit
public class BitChecker {
// Kiểm tra bit thứ i có là 1 không
public static boolean getBit(int num, int i) {
return ((num & (1 << i)) != 0);
}
// Đếm số bit 1
public static int countSetBits(int num) {
int count = 0;
while (num != 0) {
count += num & 1;
num >>>= 1;
}
return count;
}
// Kiểm tra số có phải là lũy thừa của 2
public static boolean isPowerOfTwo(int num) {
return num > 0 && (num & (num - 1)) == 0;
}
}
3.2. Thay đổi bit
public class BitModifier {
// Set bit thứ i thành 1
public static int setBit(int num, int i) {
return num | (1 << i);
}
// Clear bit thứ i thành 0
public static int clearBit(int num, int i) {
return num & ~(1 << i);
}
// Toggle bit thứ i
public static int toggleBit(int num, int i) {
return num ^ (1 << i);
}
// Clear tất cả bit từ MSB đến i
public static int clearMSBtoI(int num, int i) {
return num & ((1 << i) - 1);
}
// Clear tất cả bit từ i đến 0
public static int clearIto0(int num, int i) {
return num & (-1 << (i + 1));
}
}
3.3. Các thuật toán nâng cao
public class AdvancedBitManipulation {
// Đảo ngược các bit
public static int reverseBits(int num) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (num & 1);
num >>>= 1;
}
return result;
}
// Tìm bit 1 đầu tiên từ phải sang
public static int getFirstSetBit(int num) {
return num & -num;
}
// Hoán đổi các bit chẵn và lẻ
public static int swapEvenOddBits(int num) {
return ((num & 0xAAAAAAAA) >>> 1) | ((num & 0x55555555) << 1);
}
// Tìm số xuất hiện một lần trong mảng mà các số khác xuất hiện hai lần
public static int findSingle(int[] arr) {
int result = 0;
for (int num : arr) {
result ^= num;
}
return result;
}
}
4. Ứng dụng thực tế
- Tối ưu hóa bộ nhớ
- Mã hóa và giải mã
- Nén dữ liệu
- Xử lý hình ảnh
- Kiểm tra và sửa lỗi
- Network protocols
- Embedded systems
5. Bài tập thực hành
- Implement các hàm cơ bản:
- Đếm số bit 1 trong một số
- Kiểm tra số chẵn/lẻ không dùng %
-
Đảo ngược các bit
-
Bài tập nâng cao:
- Tìm số thiếu trong dãy số từ 1 đến n
- Tìm hai số xuất hiện một lần trong mảng
-
Tính tổng hai số không dùng phép cộng
-
Ứng dụng thực tế:
- Implement một bitmap đơn giản
- Tạo bộ lọc Bloom đơn giản
- Nén chuỗi sử dụng bit manipulation
6. Tối ưu hóa
- Sử dụng lookup table cho các thao tác phổ biến
- Tận dụng các tính chất toán học
- Sử dụng parallel processing khi có thể
- Cache các kết quả trung gian
7. Lưu ý và best practices
- Luôn kiểm tra overflow
- Cẩn thận với dấu của số
- Xem xét endianness khi làm việc với bytes
- Document code rõ ràng vì bit manipulation khó đọc
- Sử dụng hằng số có ý nghĩa thay vì magic numbers