Bit Manipulation - The Low-Level Wizardry

"Bit manipulation là ngôn ngữ của CPU. Hiểu nó = Hiểu máy tính thực sự hoạt động thế nào." - HPN

Tại sao cần Bit Manipulation?

Benefit	Example
Speed	Bitwise ops nhanh hơn arithmetic 10-100x
Memory	Lưu 32 flags trong 1 integer thay vì 32 booleans
Cryptography	XOR là foundation của encryption
Compression	Huffman, LZ algorithms
Graphics	Color manipulation, alpha blending

Basic Bitwise Operators

# AND (&): 1 if BOTH bits are 1
0b1010 & 0b1100  # = 0b1000 (8)

# OR (|): 1 if ANY bit is 1
0b1010 | 0b1100  # = 0b1110 (14)

# XOR (^): 1 if bits are DIFFERENT
0b1010 ^ 0b1100  # = 0b0110 (6)

# NOT (~): Flip all bits
~0b1010  # = -11 (two's complement)

# Left Shift (<<): Multiply by 2^n
5 << 2  # = 20 (5 * 4)

# Right Shift (>>): Divide by 2^n
20 >> 2  # = 5 (20 / 4)

Module Contents

XOR Magic

• Swap without temp
• Find single non-duplicate
• Missing number in sequence

Bitmasking

• Subset generation
• RBAC permissions
• State compression

Fast Exponentiation

• A^B % M in O(log B)
• RSA cryptography foundation
• Matrix exponentiation

Quick Reference

Operation	Code	Use Case
Check bit i	(n >> i) & 1	Is feature enabled?
Set bit i	n | (1 << i)	Enable feature
Clear bit i	n & ~(1 << i)	Disable feature
Toggle bit i	n ^ (1 << i)	Switch feature
Get lowest set bit	n & (-n)	Fenwick Tree, LSB
Clear lowest set bit	n & (n-1)	Count set bits
Check power of 2	n & (n-1) == 0	Memory alignment
All 1s (n bits)	(1 << n) - 1	Bitmask

💡 HPN's Rule

"Thấy 'subset', 'XOR', 'flags', 'permissions' → Bit manipulation. Nhanh hơn, gọn hơn, đẹp hơn."