Chương 21 - Bit Manipulation + Mask

Bit manipulation mở ra giải pháp O(1) cho nhiều bài tưởng O(n). Tricks XOR, AND, OR + bit-shift là ngôn ngữ thứ 2 của lập trình viên. Chương này dạy 6 bài kinh điển + bit tricks bạn cần thuộc. Bitmask sẽ được mở rộng ở Chương 40 (Bitmask DP) và 41 (Bitmask + Trie).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Thuộc 10 bit tricks: set/clear/toggle/test, lowest set bit x & -x, Brian Kernighan x & (x-1).
  • XOR property: a ^ a = 0 → tìm single number / cặp khác bit.
  • Greedy bit from highest cho Max XOR.
  • Cẩn thận với số âm trong Python: mask 32-bit khi cần two’s complement.

Khi nào dùng pattern này?

  • Có ràng buộc set / subset nhỏ (≤ 20 phần tử).
  • Cần thao tác toggle / count / lookup bit nhanh.
  • Bài XOR đặc thù: tìm “single number”, “pair with max XOR”.
  • Tối ưu space - int 32-bit chứa 32 boolean.

Bit tricks cheat-sheet 

# Set bit i:                     x |= (1 << i)
# Clear bit i:                   x &= ~(1 << i)
# Toggle bit i:                  x ^= (1 << i)
# Test bit i:                    (x >> i) & 1
# Lowest set bit (rightmost 1):  x & -x      (ví dụ x=12=0b1100 → 4=0b100)
# Pop lowest set bit:            x &= x - 1
# Count set bits:                bin(x).count('1')   # hoặc x.bit_count() Py3.10+

# Iterate qua subsets của mask:
sub = mask
while sub:
    # ... use sub ...
    sub = (sub - 1) & mask

# Kiểm tra power of 2:           x > 0 and (x & (x - 1)) == 0
# Đảo bit 32-bit:                xor với 0xFFFFFFFF

Bài tự luyện cuối chương

  • LC 137 - Single Number II (mỗi số 3 lần, 1 số 1 lần)
  • LC 190 - Reverse Bits
  • LC 260 - Single Number III
  • LC 268 - Missing Number
  • LC 461 - Hamming Distance
  • LC 1290 - Convert Binary Number in a Linked List

21.1 Single Number (LC 136)

Đề bài

Cho mảng nums, mỗi phần tử xuất hiện 2 lần trừ đúng 1 phần tử xuất hiện 1 lần. Tìm phần tử đó. O(n) time, O(1) space.

Ví dụ 

Input:  nums = [2, 2, 1]            → Output: 1
Input:  nums = [4, 1, 2, 1, 2]      → Output: 4
(mọi phần tử xuất hiện đúng 2 lần trừ một phần tử duy nhất xuất hiện 1 lần)

Ràng buộc

  • 1 <= len(nums) <= 3·10^4
  • Mỗi phần tử (trừ 1) xuất hiện 2 lần

Clarifying questions

  • Mảng rỗng? → Không xảy ra (theo đề ≥ 1).
  • Tất cả số đều xuất hiện 2 lần (không có single)? → Không xảy ra (theo đề).

Hướng tiếp cận

Trick XOR: a XOR a = 0; a XOR 0 = a. XOR có tính giao hoán & kết hợp. XOR cả mảng → các cặp huỷ nhau, còn lại = phần tử cô độc.

Code Python 3 

from typing import List
from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Vì sao trick này đẹp: tận dụng tính chất đại số của XOR. Hash table cũng làm được O(n) nhưng tốn O(n) space.
  • Follow-up: LC 137 (3 lần + 1 lần)
    • đếm bit theo modulo 3. LC 260 (2 số single) - XOR all rồi tách 2 nhóm theo 1 bit khác nhau.

Bài tự luyện liên quan

  • LC 137, 260 - Single Number II, III.
  • LC 268 - Missing Number.

21.2 Number of 1 Bits (LC 191)

Đề bài

Cho số nguyên n. Trả về số bit 1 trong biểu diễn nhị phân (Hamming weight).

Ví dụ 

Input:  n = 11 (0b1011)   → 3
Input:  n = 128 (0b10000000) → 1

Ràng buộc

  • 0 <= n <= 2^31-1

Clarifying questions

  • n âm? → Theo đề LC: 0 ≤ n; nếu cần xử lý two’s complement thì mask trước.

Hướng tiếp cận

Cách 1 - Loop bit, O(32). Cách 2 - Trick n &= n - 1, O(số bit 1). Mỗi lần n & (n-1) xoá bit 1 thấp nhất.

Hình minh hoạ - n = 12 = 0b1100:

n = 1100
n-1=1011
n & (n-1) = 1000  → count = 1

n = 1000
n-1=0111
n & (n-1) = 0000  → count = 2

n = 0, dừng. Tổng 2 bit 1.  ✓

Code Python 3 

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

Phân tích độ phức tạp

  • Thời gian: O(số bit 1) ≤ 32. Bộ nhớ: O(1).

Bình luận

  • Python 3.10+ có int.bit_count() - built-in O(1) thực tế. Khi phỏng vấn nên trình bày trick n & (n-1) để chứng tỏ hiểu.

Bài tự luyện liên quan

  • LC 461 - Hamming Distance.
  • LC 477 - Total Hamming Distance.

21.3 Counting Bits (LC 338)

Đề bài

Cho n. Trả về mảng result dài n + 1, result[i] = số bit 1 của i.

Ví dụ 

Input:  n = 5
Output: [0, 1, 1, 2, 1, 2]

Ràng buộc

  • 0 <= n <= 10^5

Clarifying questions

  • n = 0? → Trả [0].

Hướng tiếp cận

Brute force - gọi hammingWeight(i) cho mỗi i, O(n log n).

DP - O(n): result[i] = result[i >> 1] + (i & 1).

Trực giác: bit 1 của i = bit 1 của i >> 1 (đã trừ bit cuối) + bit cuối.

Hoặc: result[i] = result[i & (i-1)] + 1.

Code Python 3 

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        result = [0] * (n + 1)
        for i in range(1, n + 1):
            result[i] = result[i >> 1] + (i & 1)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

  • Đây là DP “đứng vai khổng lồ”: kết quả của i dựa trên kết quả i đã tính nhỏ hơn.

Bài tự luyện liên quan

  • LC 191 - Number of 1 Bits.
  • LC 1356 - Sort Integers by The Number of 1 Bits.

21.4 Sum of Two Integers (LC 371)

Đề bài

Tính a + b không dùng + hoặc -.

Ví dụ 

Input:  a = 1, b = 2   → 3
Input:  a = 2, b = 3   → 5

Ràng buộc

  • -1000 <= a, b <= 1000

Clarifying questions

  • a, b âm? → Cần xử lý mask 32-bit.

Hướng tiếp cận

Insight: - a XOR b = tổng các bit không carry. - (a AND b) << 1 = carry. - Lặp đến khi carry = 0.

Code Python 3 

class Solution:
    MASK = 0xFFFFFFFF

    def getSum(self, a: int, b: int) -> int:
        while b:
            carry = (a & b) << 1
            a = (a ^ b) & self.MASK
            b = carry & self.MASK
        # Xử lý số âm trong Python (int vô hạn).
        return a if a < 0x80000000 else ~(a ^ self.MASK)

Phân tích độ phức tạp

  • Thời gian: O(32). Bộ nhớ: O(1).

Bình luận

  • Python int vô hạn → cần dùng MASK = 0xFFFFFFFF để mô phỏng 32-bit.
  • Số âm Python lưu dạng Two’s complement vô hạn - phải convert lại sau.

Bài tự luyện liên quan

  • LC 7 - Reverse Integer.
  • LC 29 - Divide Two Integers.

21.5 Bitwise AND of Numbers Range (LC 201)

Đề bài

Cho left, right. Trả về AND của tất cả số trong [left, right].

Ví dụ 

Input:  left = 5 (0b101), right = 7 (0b111)
Output: 4 (0b100)
Giải thích: 5 & 6 & 7 = 100 & 110 & 111 = 100 = 4.

Ràng buộc

  • 0 <= left <= right <= 2^31-1

Clarifying questions

  • left = right? → Trả left.
  • left = 0? → Trả 0.

Hướng tiếp cận

Insight: AND của range = prefix chung của left và right ở dạng nhị phân, padded zero ở các bit thấp hơn.

Vì khi range qua nhiều giá trị, các bit thấp đều có lúc bằng 0 → AND = 0.

Cách: shift cả 2 sang phải đến khi left == right (tìm prefix chung), rồi shift trái lại.

Code Python 3 

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shifts = 0
        while left < right:
            left >>= 1
            right >>= 1
            shifts += 1
        return left << shifts

Phân tích độ phức tạp

  • Thời gian: O(log right). Bộ nhớ: O(1).

Bình luận

  • Brian Kernighan’s trick (variant): right &= (right - 1) cho đến khi right < left. Tương đương nhưng đẹp hơn.

Bài tự luyện liên quan

  • LC 477 - Total Hamming Distance.

21.6 Maximum XOR of Two Numbers in an Array (LC 421)

Đề bài

Cho nums. Trả về XOR lớn nhất của 2 phần tử khác nhau.

Ví dụ 

Input:  nums = [3, 10, 5, 25, 2, 8]
Output: 28
Giải thích: 5 XOR 25 = 28.

Ràng buộc

  • 2 <= len(nums) <= 2·10^5
  • 0 <= nums[i] <= 2^31-1

Clarifying questions

  • Mảng < 2 phần tử? → Theo đề: ≥ 2.

Hướng tiếp cận

Brute force - O(n²). Mọi cặp.

Trick “Greedy bit” - O(n · 32).

Xây kết quả từng bit từ cao xuống thấp. Tại bit b: - Giả sử kết quả từ bit cao đến b+1 đã là result. - Thử mở bit b: candidate = result | (1 << b). - Kiểm tra: tồn tại cặp (a, b) trong nums với (a ^ b) & mask == candidate không? (mask = các bit ≥ b)

  • Cách check: tạo prefixes = {x & mask for x in nums}. Với mỗi prefix p, check p ^ candidate in prefixes.

Nếu có → giữ candidate; không có → giữ result cũ.

Trie approach (Chương 41) cũng làm được - đó là extension.

Code Python 3 

from typing import List

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        result = 0
        mask = 0
        for b in range(31, -1, -1):
            mask |= (1 << b)
            prefixes = {x & mask for x in nums}
            candidate = result | (1 << b)
            for p in prefixes:
                if p ^ candidate in prefixes:
                    result = candidate
                    break
        return result

Phân tích độ phức tạp

  • Thời gian: O(n · 32) = O(n). Bộ nhớ: O(n).

Bình luận

  • Greedy bit trên XOR là pattern hay tái xuất. Khi gặp “max XOR” → suy nghĩ greedy bit + set.
  • Cách Trie đẹp hơn cho biến thể “có constraint”: LC 1707, LC 1803.

Bài tự luyện liên quan

  • LC 1707 - Maximum XOR With an Element From Array (Chương 41).
  • LC 1803 - Count Pairs With XOR in a Range.

Tóm tắt chương & Quyết định

Python signed int caveat (LC 371 Sum of Two Integers)

Python int vô hạn bit → (-1) << 1 không tràn. Để mô phỏng C++ 32-bit:

MASK = 0xFFFFFFFF
INT_MIN_NEG = 0x80000000
while b:
    a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
return a if a < INT_MIN_NEG else ~(a ^ MASK)

Counting Bits - 2 recurrence

  • dp[i] = dp[i >> 1] + (i & 1): dùng bit cao nhất + lsb.
  • dp[i] = dp[i & (i - 1)] + 1: trick i & (i-1) xoá bit thấp nhất ⇒ “subproblem = i bỏ 1 bit”. Cả hai O(n); chọn cái nào dễ giải thích hơn cho interviewer.

Range AND (LC 201) - common prefix

  • [m, n] AND của tất cả số = prefix nhị phân chung dài nhất của m và n, các bit thấp còn lại = 0.
  • Trick: shift cả hai sang phải đến khi bằng nhau, đếm số bước → shift trái lại.

Bài LC 421 (Max XOR of Two Numbers) là gateway cho Binary Trie trong Chương 41 (Bitmask + Trie). Mỗi số = đường đi 32 bit trong trie; greedy chọn bit ngược lại để maximize XOR.