Các mẹo bit manipulation phổ biến là gì?

Question

Accepted Answer

**Bit manipulation** (thao tác bit) làm việc trực tiếp trên biểu diễn nhị phân của các số nguyên bằng AND, OR, XOR, NOT, và các phép dịch (shift). Nó cho phép các thao tác gọn gàng, không phân nhánh (branch-free), và rất nhanh. ## Các thao tác cốt lõi ```python x & 1 # x có lẻ không? (bit thấp nhất) x << 1 # nhân với 2 x >> 1 # chia nguyên cho 2 x & (1 << k) # bit thứ k có được bật không? x | (1 << k) # bật bit thứ k x & ~(1 << k) # xóa bit thứ k x ^ (1 << k) # đảo bit thứ k ``` ## Các mẹo hữu ích ```python x & (x - 1) # xóa bit được bật thấp nhất x & (x - 1) == 0 # x có phải lũy thừa của 2 không? (x>0) x & (-x) # cô lập bit được bật thấp nhất bin(x).count('1') # popcount (số bit được bật) ``` ## Ví dụ: tìm số đơn lẻ (mẹo XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # các cặp triệt tiêu: a ^ a == 0 return result # giá trị lẻ loi duy nhất còn lại single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Độ phức tạp Các phép bit là O(1); phép quét XOR ở trên là **O(n) thời gian, O(1) bộ nhớ**. ## Khi nào dùng / những cạm bẫy Dùng cho **bitmask** (liệt kê tập con, DP trên các trạng thái), cờ (flag), toán học nhanh, và code mức thấp/nhúng. Cẩn thận với bit dấu, hành vi dịch bit đặc thù theo ngôn ngữ, và độ dễ đọc — hãy chú thích các mẹo không hiển nhiên. ## Tại sao điều này quan trọng Bit manipulation cho ra các lời giải O(1) bộ nhớ thanh thoát (như mẹo XOR tìm số đơn lẻ) gây kinh ngạc trong phỏng vấn. Bitmask DP làm cho nhiều bài toán không gian trạng thái tổ hợp trở nên khả thi. Nó thiết yếu trong hệ thống, đồ họa, nén dữ liệu, và code đòi hỏi hiệu năng cao nơi mỗi chu kỳ đều quý giá.