02-Bit-Manipulation

Buổi 02 — Bit Manipulation

Navigation

← 01-Two-Pointers-Sliding-Window | → 03-Monotonic-Stack-Queue Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

---

1. Analogy & Context

Light Switch Analogy

Bit manipulation = làm việc với công tắc đèn.

• 0 = tắt (OFF), 1 = bật (ON)
• AND (&) = cả hai công tắc đều phải bật → đèn mới sáng
• OR (|) = ít nhất một công tắc bật → đèn sáng
• XOR (^) = đúng một công tắc bật → “toán tử khác nhau”
• NOT (~) = đảo trạng thái
• Left shift (<<) = nhân 2 (thêm số 0 vào bên phải)
• Right shift (>>) = chia 2 (bỏ bit cuối bên phải)

Tại sao học Bit Manipulation?

Trong thực tế hệ thống, bit manipulation xuất hiện ở:

• Space optimization: lưu 64 flags trong một số 64-bit thay vì 64 boolean
• Cryptography & hashing: XOR là nền tảng của nhiều cipher
• Competitive programming: bitmask DP cho NP-hard problems trên small N
• Embedded systems & graphics: pixel blending, shader programming
• Networking: subnet masks, IP address operations

FAANG Signal

XOR trick cho “find single number” là câu hỏi phổ biến ở Google, Amazon, Meta. Nếu bạn không biết bit manipulation, bạn sẽ giải O(N) space thay vì O(1) space.

---

2. The FAANG Standard

Những gì interviewer kỳ vọng ở level L4-L5:

Skill	Description
Basic ops	Nhận ra khi nào dùng &, `
Power-of-2 check	n & (n-1) == 0 — giải thích được tại sao
XOR self-cancellation	a ^ a = 0, a ^ 0 = a
Bitmask enumeration	Enumerate all $2^N$ subsets
Brian Kernighan	Count set bits trong O(number of set bits)
Bit tricks	Get/set/clear/toggle specific bit

Key identities cần thuộc lòng:

a ^ a = 0          (XOR với chính nó = 0)
a ^ 0 = a          (XOR với 0 = giữ nguyên)
a & (a-1)          (xóa lowest set bit)
a & (-a)           (giữ chỉ lowest set bit)
a | (a-1)          (set tất cả bit từ lowest xuống)
(a >> k) & 1       (lấy bit thứ k)
a | (1 << k)       (set bit thứ k)
a & ~(1 << k)      (clear bit thứ k)
a ^ (1 << k)       (toggle bit thứ k)

---

3. Visual Thinking (Mermaid)

3.1 Truth Tables

graph TD
    subgraph AND
        A1["0 & 0 = 0"]
        A2["0 & 1 = 0"]
        A3["1 & 0 = 0"]
        A4["1 & 1 = 1"]
    end
    subgraph OR
        O1["0 | 0 = 0"]
        O2["0 | 1 = 1"]
        O3["1 | 0 = 1"]
        O4["1 | 1 = 1"]
    end
    subgraph XOR
        X1["0 ^ 0 = 0"]
        X2["0 ^ 1 = 1"]
        X3["1 ^ 0 = 1"]
        X4["1 ^ 1 = 0"]
    end

3.2 Left/Right Shift Visualization

graph LR
    A["5 = 0000 0101"] -->|"<< 1 (x2)"| B["10 = 0000 1010"]
    B -->|"<< 1 (x2)"| C["20 = 0001 0100"]
    C -->|">> 1 (÷2)"| D["10 = 0000 1010"]
    D -->|">> 1 (÷2)"| E["5 = 0000 0101"]

3.3 Brian Kernighan’s Algorithm — Count Set Bits

flowchart TD
    Start["n = 13 = 1101₂, count = 0"] --> Step1
    Step1["n & n-1 = 1101 & 1100 = 1100<br/>count = 1, n = 12"] --> Step2
    Step2["n & n-1 = 1100 & 1011 = 1000<br/>count = 2, n = 8"] --> Step3
    Step3["n & n-1 = 1000 & 0111 = 0000<br/>count = 3, n = 0"] --> Done
    Done["n = 0, return count = 3"]

    style Start fill:#4a9eff,color:#fff
    style Done fill:#22c55e,color:#fff

Insight

n & (n-1) luôn xóa lowest set bit của n. Vì vậy số lần lặp = số lượng set bits (1s) trong n, không phải tổng số bits.

---

4. TypeScript Template

4.1 Basic Bit Operations

// ============================================================
// BASIC BIT OPERATIONS — Reference Sheet
// ============================================================
 
const n = 0b1101; // 13 in binary
 
// --- Kiểm tra bit thứ k (0-indexed từ phải) ---
const getBit = (n: number, k: number): number => (n >> k) & 1;
// getBit(13, 0) = 1 (bit 0 = 1 trong 1101)
// getBit(13, 1) = 0 (bit 1 = 0 trong 1101)
 
// --- Set bit thứ k lên 1 ---
const setBit = (n: number, k: number): number => n | (1 << k);
// setBit(13, 1) = 1101 | 0010 = 1111 = 15
 
// --- Clear bit thứ k về 0 ---
const clearBit = (n: number, k: number): number => n & ~(1 << k);
// clearBit(13, 0) = 1101 & 1110 = 1100 = 12
 
// --- Toggle bit thứ k ---
const toggleBit = (n: number, k: number): number => n ^ (1 << k);
// toggleBit(13, 1) = 1101 ^ 0010 = 1111 = 15
 
// --- Lowest set bit ---
const lowestSetBit = (n: number): number => n & (-n);
// lowestSetBit(12) = 1100 & 0100 = 0100 = 4
 
// --- Remove lowest set bit (Brian Kernighan trick) ---
const removeLowestSetBit = (n: number): number => n & (n - 1);
// removeLowestSetBit(12) = 1100 & 1011 = 1000 = 8

4.2 isPowerOfTwo — O(1)

// LeetCode #231
// Insight: 2^k có đúng 1 bit = 1. Vì vậy n & (n-1) = 0.
// Edge case: n <= 0 không phải power of two.
function isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
}
 
// Examples:
// isPowerOfTwo(8)  = 1000 & 0111 = 0 → true
// isPowerOfTwo(6)  = 0110 & 0101 = 0100 ≠ 0 → false
// isPowerOfTwo(1)  = 0001 & 0000 = 0 → true (2^0 = 1)

4.3 Single Number — XOR Trick, O(N) time O(1) space

// LeetCode #136
// Insight: a ^ a = 0, a ^ 0 = a
// XOR tất cả elements: cặp đôi tự triệt tiêu, số lẻ còn lại
function singleNumber(nums: number[]): number {
    return nums.reduce((xor, num) => xor ^ num, 0);
}
 
// Example: [4, 1, 2, 1, 2]
// 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2
// = 4 ^ (1^1) ^ (2^2)
// = 4 ^ 0 ^ 0 = 4  ✓

4.4 Hamming Weight (Count Set Bits)

// LeetCode #191
 
// Approach 1: Naive O(log N) — loop qua từng bit
function hammingWeightNaive(n: number): number {
    let count = 0;
    while (n !== 0) {
        count += n & 1;     // kiểm tra bit cuối
        n = n >>> 1;        // unsigned right shift (quan trọng trong JS!)
    }
    return count;
}
 
// Approach 2: Brian Kernighan O(k) — k = số set bits
// Luôn nhanh hơn hoặc bằng naive (k <= log N)
function hammingWeight(n: number): number {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1);    // xóa lowest set bit
        count++;
    }
    return count;
}
 
// Example: n = 13 = 1101
// Iteration 1: 1101 & 1100 = 1100 (n=12), count=1
// Iteration 2: 1100 & 1011 = 1000 (n=8),  count=2
// Iteration 3: 1000 & 0111 = 0000 (n=0),  count=3 → return 3

4.5 Reverse Bits

// LeetCode #190
// Approach: lấy bit cuối của n, đặt vào vị trí tương ứng của result
function reverseBits(n: number): number {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // shift result left, append bit của n
        n = n >>> 1;                        // unsigned shift n right
    }
    return result >>> 0;    // convert to unsigned 32-bit
}
 
// Trực quan:
// n =      1011 0000 0000 0000 0000 0000 0000 0011
// result = 1100 0000 0000 0000 0000 0000 0000 1101

4.6 Subsets via Bitmask Enumeration

// LeetCode #78
// Key: với N elements, có 2^N subsets.
// Bitmask i từ 0 đến 2^N - 1: bit thứ j = 1 → element j có mặt trong subset.
function subsets(nums: number[]): number[][] {
    const n = nums.length;
    const result: number[][] = [];
 
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset: number[] = [];
        for (let j = 0; j < n; j++) {
            if ((mask >> j) & 1) {      // bit j của mask = 1?
                subset.push(nums[j]);
            }
        }
        result.push(subset);
    }
 
    return result;
}
 
// Example: nums = [1, 2, 3]
// mask=000 (0): []
// mask=001 (1): [1]
// mask=010 (2): [2]
// mask=011 (3): [1,2]
// mask=100 (4): [3]
// mask=101 (5): [1,3]
// mask=110 (6): [2,3]
// mask=111 (7): [1,2,3]
// Total: 8 = 2^3 subsets ✓

4.7 Missing Number — XOR Trick

// LeetCode #268
// Approach: XOR index 0..n với tất cả elements
// Số nào xuất hiện đúng 2 lần (một lần trong index, một lần trong array) sẽ bị triệt tiêu
// Số thiếu chỉ xuất hiện 1 lần (trong index) → còn lại
function missingNumber(nums: number[]): number {
    let xor = nums.length;          // bắt đầu với n (index cuối)
    for (let i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];         // XOR với cả index lẫn value
    }
    return xor;
}
 
// Example: nums = [3, 0, 1]  (n=3, missing=2)
// xor = 3 ^ (0^3) ^ (1^0) ^ (2^1) = 3^3^0^0^1^2^1 = 2 ✓

---

5. Complexity Deep-dive

Operation	Time	Space	Notes
Single bit op (&, `	, ^`)	$O(1)$	$O(1)$
isPowerOfTwo	$O(1)$	$O(1)$	Single bit trick
singleNumber	$O(N)$	$O(1)$	XOR toàn bộ array
hammingWeight (naive)	$O(\log N)$	$O(1)$	Loop qua 32 bits
hammingWeight (Kernighan)	$O(k)$	$O(1)$	k = số set bits ≤ log N
reverseBits	$O(1)$	$O(1)$	Fixed 32 iterations
subsets (bitmask)	$O(2^N\cdot N)$	$O(2^N\cdot N)$	$2^N$ masks, N bits each
missingNumber	$O(N)$	$O(1)$	XOR trick

Why Kernighan is Faster

Nếu n = 1000 0000 0000 0000 (chỉ 1 set bit), naive cần 16 iterations (loop 16 bits), Kernighan chỉ cần 1 iteration. Với số thưa bit, Kernighan thắng đáng kể.

Bitmask DP: Với N ≤ 20, bitmask DP chạy trong $O(2^N\cdot N)$ — chậm nhưng chấp nhận được. Với N > 20, không feasible.

---

6. Edge Cases & Pitfalls

JavaScript >>> vs >>

Trong JavaScript, tất cả bitwise operators làm việc với 32-bit signed integers.

• >> = arithmetic right shift (giữ sign bit — vấn đề với số âm!)
• >>> = logical (unsigned) right shift (luôn thêm 0 vào trái)

(-1) >> 1   = -1   // arithmetic: -1 = 11...1, shift right giữ 1
(-1) >>> 1  = 2147483647  // logical: thêm 0 vào trái

Rule: Dùng >>> khi muốn treat number là unsigned 32-bit.

Two's Complement — Số Âm

Trong two’s complement:

• -1 = 1111...1111 (32 ones)
• -n = ~n + 1 (flip all bits, then add 1)
• ~n = -(n+1) luôn đúng

Điều này ảnh hưởng đến mọi operation với số âm!

n & (n-1) — Hiểu Đúng

n & (n-1) xóa lowest SET bit (không phải lowest 0 bit).

n   = 1100
n-1 = 1011
&   = 1000   ← lowest set bit (bit 2) đã bị xóa

Bit Shift Overflow trong JS

• Bit shift trong JS là modulo 32: 1 << 32 === 1 (không phải 0!)
• Tức là (1 << 31) là số âm trong signed 32-bit: -2147483648
• Để check N phần tử, dùng 1 << N chỉ safe khi N < 31

Off-by-One trong Bitmask

• Mask cho N phần tử: (1 << N) = số masks (exclusive upper bound)
• Full mask (tất cả N bits = 1): (1 << N) - 1
• Ví dụ N=3: masks từ 000 đến 111, tức 0 đến 7 = (1<<3)-1

---

7. Pattern Recognition

Nhận Dạng Bài Toán Bit Manipulation

“Find single number among duplicates” → XOR tất cả elements (pairs cancel out) → Variant: “find two singles” → XOR, find differing bit, partition

“Is power of two / four” → n > 0 && (n & (n-1)) === 0 for power of two → Plus (n & 0xAAAAAAAA) === 0 for power of four (bits in odd positions)

“Count 1s in binary representation” → Brian Kernighan’s algorithm

“Missing number in 0..n” → XOR trick: index XOR value, duplicates cancel

“All subsets / enumerate bitmasks” → Loop mask from 0 to (1 << N) - 1 → Check each bit: (mask >> j) & 1

“XOR of range [0..n]” → Pattern: XOR(0..n) cycles as n%4: [n, 1, n+1, 0]

“Swap without temp variable” → a ^= b; b ^= a; a ^= b; (classic interview trick)

---

8. Top LeetCode Problems

#	Problem	Difficulty	Key Trick
LC-136 #136	Single Number	Easy	XOR all elements
LC-191 #191	Number of 1 Bits	Easy	Brian Kernighan
LC-190 #190	Reverse Bits	Easy	Loop 32 times
LC-268 #268	Missing Number	Easy	XOR index + value
LC-78 #78	Subsets	Medium	Bitmask enumeration
LC-231 #231	Power of Two	Easy	n & (n-1) == 0
LC-137 #137	Single Number II	Medium	Bit counting mod 3
LC-260 #260	Single Number III	Medium	XOR + partition

Complete Solution: All Subsets of [1, 2, 3] with Explanation

// LeetCode #78 — Subsets
// Input: nums = [1, 2, 3]
// Expected: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
 
function subsetsComplete(nums: number[]): number[][] {
    const n = nums.length;          // n = 3
    const totalMasks = 1 << n;      // 1 << 3 = 8 (2^3 subsets)
    const result: number[][] = [];
 
    // Iterate through all 2^n bitmasks
    for (let mask = 0; mask < totalMasks; mask++) {
        const subset: number[] = [];
 
        // For each bit position j, check if element j is included
        for (let j = 0; j < n; j++) {
            if ((mask >> j) & 1) {
                // Bit j is set → include nums[j]
                subset.push(nums[j]);
            }
        }
 
        result.push(subset);
    }
 
    return result;
}
 
/*
STEP-BY-STEP for nums = [1, 2, 3]:
 
mask=0 (binary: 000):
  j=0: (000 >> 0) & 1 = 0 → skip
  j=1: (000 >> 1) & 1 = 0 → skip
  j=2: (000 >> 2) & 1 = 0 → skip
  subset = []  ← empty set
 
mask=1 (binary: 001):
  j=0: (001 >> 0) & 1 = 1 → include nums[0]=1
  j=1: (001 >> 1) & 1 = 0 → skip
  j=2: (001 >> 2) & 1 = 0 → skip
  subset = [1]
 
mask=2 (binary: 010):
  j=0: (010 >> 0) & 1 = 0 → skip
  j=1: (010 >> 1) & 1 = 1 → include nums[1]=2
  j=2: (010 >> 2) & 1 = 0 → skip
  subset = [2]
 
mask=3 (binary: 011):
  j=0: (011 >> 0) & 1 = 1 → include nums[0]=1
  j=1: (011 >> 1) & 1 = 1 → include nums[1]=2
  j=2: (011 >> 2) & 1 = 0 → skip
  subset = [1, 2]
 
mask=4 (binary: 100):
  j=0: (100 >> 0) & 1 = 0 → skip
  j=1: (100 >> 1) & 1 = 0 → skip
  j=2: (100 >> 2) & 1 = 1 → include nums[2]=3
  subset = [3]
 
mask=5 (binary: 101):
  j=0: (101 >> 0) & 1 = 1 → include nums[0]=1
  j=1: (101 >> 1) & 1 = 0 → skip
  j=2: (101 >> 2) & 1 = 1 → include nums[2]=3
  subset = [1, 3]
 
mask=6 (binary: 110):
  j=0: (110 >> 0) & 1 = 0 → skip
  j=1: (110 >> 1) & 1 = 1 → include nums[1]=2
  j=2: (110 >> 2) & 1 = 1 → include nums[2]=3
  subset = [2, 3]
 
mask=7 (binary: 111):
  j=0: (111 >> 0) & 1 = 1 → include nums[0]=1
  j=1: (111 >> 1) & 1 = 1 → include nums[1]=2
  j=2: (111 >> 2) & 1 = 1 → include nums[2]=3
  subset = [1, 2, 3]  ← full set
 
RESULT: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Total: 8 subsets = 2^3 ✓
 
Time:  O(2^N * N) — 2^N masks, N bits to check each
Space: O(2^N * N) — storing all subsets
*/

---

9. Self-Assessment Checklist

Checklist sau khi học Bit Manipulation

• Giải thích được tại sao n & (n-1) === 0 kiểm tra power of two
• Viết hammingWeight bằng Brian Kernighan không nhìn note
• Giải thích a ^ a = 0 và ứng dụng vào singleNumber
• Implement bitmask enumeration cho N phần tử
• Biết khi nào dùng >>> thay vì >> trong JavaScript
• Giải được #136, #191, #268 trong < 5 phút mỗi bài
• Giải được #78 Subsets bằng bitmask (không chỉ backtracking)
• Giải thích two’s complement ảnh hưởng thế nào đến bitwise ops
• Biết XOR trick cho “missing number” và variants

Luyện tập tiếp theo

Sau khi nắm vững các trick cơ bản, thử challenge:

• #137 Single Number II (numbers appear 3 times, find the one appearing once)
• #260 Single Number III (two singles)
• #421 Maximum XOR of Two Numbers (Trie + bit)
• Bitmask DP: #847 Shortest Path Visiting All Nodes

---

Tags: dsa bit-manipulation xor bitmask faang-mastery Related: 01-Two-Pointers-Sliding-Window | 03-Monotonic-Stack-Queue | Pattern-Bit-Tricks