Bit Hacking Toàn Tập - Phần 2: Tối Ưu Cấp Cao, SIMD Tư Duy Và Những "Cú Lừa" CPU
Nếu phần 1 tập trung vào các kỹ thuật nền tảng, thì phần 2 này sẽ đi sâu vào tư duy tối ưu cấp cao — nơi Bit Hacking không chỉ là mẹo, mà trở thành chiến lược thiết kế thuật toán.
Chúng ta sẽ bước vào:
- Bit-level optimization thực chiến
- Tư duy SIMD (song song dữ liệu)
- Cache-friendly tricks
- Những hack “đánh lừa CPU pipeline”
8. Bit Parallelism – Xử lý nhiều dữ liệu cùng lúc
Một số nguyên 64-bit có thể được xem như:
64 biến boolean xử lý song song trong 1 instruction
Ví dụ: So sánh 64 phần tử cùng lúc
uint64_t a = ...;
uint64_t b = ...;
// bit i = 1 nếu a[i] == b[i]
uint64_t equal = ~(a ^ b);
👉 Thay vì loop 64 lần → chỉ 1 phép XOR + NOT
8.1. Ứng dụng: Bitset DP
Trong nhiều bài toán DP:
dp[i][j] = dp[i-1][j] | dp[i-1][j-w]
Có thể tối ưu thành:
bitset<MAX> dp;
dp |= (dp << w);
👉 Từ O(N * SUM) → giảm cực mạnh nhờ bit parallel
9. SWAR – SIMD Within A Register
SWAR = xử lý nhiều giá trị nhỏ trong 1 thanh ghi
Ví dụ: Đếm bit theo block (không loop)
uint32_t v = n;
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = (v + (v >> 4)) & 0x0F0F0F0F;
v = v * 0x01010101;
int count = v >> 24;
👉 Đây là version không dùng loop của popcount
10. Bit Compression / Packing
Ý tưởng:
Nhét nhiều giá trị nhỏ vào 1 integer
Ví dụ: lưu 4 số 8-bit trong 1 int
uint32_t pack = (a << 24) | (b << 16) | (c << 8) | d;
Giải nén:
int a = (pack >> 24) & 0xFF;
int b = (pack >> 16) & 0xFF;
int c = (pack >> 8) & 0xFF;
int d = pack & 0xFF;
👉 Giảm memory + tăng cache locality
11. Branchless Tricks nâng cao
11.1. Clamp không dùng if
int clamp(int x, int low, int high) {
x = x < low ? low : x;
x = x > high ? high : x;
return x;
}
👉 Bitwise version:
int clamp(int x, int low, int high) {
x = low + ((x - low) & -(x > low));
x = high ^ ((x ^ high) & -(x < high));
return x;
}
11.2. Conditional move (giả lập)
int res = a ^ ((a ^ b) & -cond);
👉 Nếu cond = 1 → chọn b, ngược lại chọn a
12. De Bruijn Sequence – Tìm vị trí bit cực nhanh
Bài toán:
Tìm index của bit 1 cuối cùng
Giải pháp:
static const int table[32] = {
0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18, 6, 11, 5, 10, 9
};
int index = table[(x & -x) * 0x077CB531U >> 27];
👉 O(1), không loop, không branch
13. Gray Code – Thứ tự "mượt" của bit
Gray Code đảm bảo:
Hai số liên tiếp chỉ khác đúng 1 bit
Encode:
int gray = n ^ (n >> 1);
Decode:
int binary = 0;
for (; gray; gray >>= 1)
binary ^= gray;
👉 Ứng dụng:
- Hardware encoding
- Tối ưu brute-force (tránh recompute toàn bộ)
14. Bitmask DP nâng cao
14.1. Traveling Salesman (TSP)
dp[mask][i] = min cost đi qua mask và kết thúc tại i
Transition:
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i])
14.2. SOS DP (Sum Over Subsets)
for (int i = 0; i < N; i++) {
for (int mask = 0; mask < (1 << N); mask++) {
if (mask & (1 << i)) {
dp[mask] += dp[mask ^ (1 << i)];
}
}
}
👉 Từ brute-force 2^N * 2^N → N * 2^N
15. Cache & Bit – Tối ưu bộ nhớ
So sánh:
| Cách | Memory | Speed |
|---|---|---|
| bool array | lớn | chậm |
| bitset | nhỏ | nhanh |
| bitmask int | cực nhỏ | cực nhanh |
👉 Bitmask:
- Fit vào register
- Không cache miss
- Không pointer dereference
16. Những sai lầm phổ biến
❌ Shift overflow
1 << 31 // undefined nếu int 32-bit signed
👉 Fix:
1LL << 31
❌ Signed vs Unsigned
x >> 31 // phụ thuộc compiler
👉 Dùng:
(uint32_t)x >> 31
❌ Premature optimization
Bit hacking nhanh thật, nhưng:
Không phải lúc nào cũng đáng dùng
17. Khi nào nên dùng Bit Hacking?
Nên dùng khi:
- Competitive Programming
- Real-time system
- Game engine
- Embedded
Không nên dùng khi:
- Code business logic
- Team lớn (khó maintain)
- Không cần tối ưu
Lời kết
Nếu phần 1 là “vũ khí”, thì phần 2 là chiến thuật.
Bit Hacking ở level này không còn là trick — mà là:
cách bạn suy nghĩ về dữ liệu, bộ nhớ và CPU
Một dev giỏi không chỉ viết code chạy đúng, mà còn hiểu:
- CPU xử lý gì
- Cache hoạt động ra sao
- Bit di chuyển như thế nào
All rights reserved
