Bitmasking — Nghệ thuật nén tập hợp vào số nguyên

Hãy tưởng tượng bạn đang xây hệ thống phân quyền cho một ứng dụng enterprise: mỗi người dùng có thể có tổ hợp bất kỳ trong 16 quyền khác nhau — READ, WRITE, DELETE, ADMIN, v.v. Lưu 16 cột boolean trong database? Truyền 16 tham số qua API? Không. Một số nguyên 16-bit duy nhất đã mã hoá toàn bộ tổ hợp quyền. Kiểm tra quyền chỉ cần phép AND — O(1), một instruction duy nhất trên CPU.

Đó chính là sức mạnh của Bitmasking: nén một tập hợp N phần tử vào một số nguyên N-bit, biến mọi phép toán tập hợp (hợp, giao, hiệu, kiểm tra thuộc) thành phép toán bitwise chạy trong một chu kỳ xung nhịp. Kỹ thuật này là xương sống của DP trạng thái nén (Bitmask DP) — giải Traveling Salesman trong O(N² × 2^N), liệt kê tổ hợp C(N, K) bằng Gosper's hack, và duyệt toàn bộ tập con của một mask trong O(3^N).

Bài viết này đi sâu từ nền tảng tới thực chiến: bạn sẽ hiểu rõ cách một integer ánh xạ sang tập hợp, thành thạo mọi phép toán bitmask, và áp dụng ngay vào hai bài toán kinh điển — TSP và hệ thống phân quyền production-grade.

Bức tranh tư duy

Hãy hình dung một bảng điều khiển N công tắc đèn. Mỗi công tắc chỉ có hai trạng thái: BẬT (1) hoặc TẮT (0). Trạng thái của toàn bộ bảng điều khiển tại một thời điểm được mô tả chính xác bởi một dãy N bit — hay nói cách khác, một số nguyên.

Bảng điều khiển 5 công tắc → 5 bit → giá trị 0..31

  Công tắc:    [4]  [3]  [2]  [1]  [0]
  Trạng thái:   1    0    1    1    0     ← số nhị phân
                ─────────────────────
  Giá trị:              10110₂ = 22

  Tập hợp tương ứng: {1, 2, 4}  (các vị trí bit = 1)

Ánh xạ Integer ↔ Tập hợp:

mask = 22  (10110₂)

  bit 4: 1 → phần tử 4 ∈ tập    ┐
  bit 3: 0 → phần tử 3 ∉ tập    │
  bit 2: 1 → phần tử 2 ∈ tập    ├─ Tập hợp = {1, 2, 4}
  bit 1: 1 → phần tử 1 ∈ tập    │
  bit 0: 0 → phần tử 0 ∉ tập    ┘

Phép toán tập hợp ↔ Phép toán bitwise:
  A ∪ B  =  a | b       (hợp)
  A ∩ B  =  a & b       (giao)
  A \ B  =  a & ~b      (hiệu)
  x ∈ A  =  a & (1<<x)  (kiểm tra thuộc)
  A ⊆ B  =  (a & b)==a  (tập con)

Quy tắc nền tảng: với N phần tử, toàn bộ 2^N tập con được biểu diễn bởi các số nguyên từ 0 đến 2^N - 1. Mỗi bit là một "công tắc" quyết định phần tử tương ứng có mặt hay vắng mặt.

Cốt lõi kỹ thuật

Các phép toán bitmask cơ bản

Bốn thao tác nền tảng trên từng bit: set (bật), clear (tắt), toggle (đảo), check (kiểm tra).

C++PythonJavaGo

cpp

#include <cstdio>

int main() {
    int mask = 0b1010; // tập {1, 3}

    // Set bit i (thêm phần tử i vào tập)
    mask |= (1 << 2);   // mask = 1110₂ = {1, 2, 3}

    // Clear bit i (xoá phần tử i khỏi tập)
    mask &= ~(1 << 1);  // mask = 1100₂ = {2, 3}

    // Toggle bit i (đảo trạng thái phần tử i)
    mask ^= (1 << 0);   // mask = 1101₂ = {0, 2, 3}

    // Check bit i (phần tử i có trong tập?)
    bool has2 = (mask >> 2) & 1; // true

    // Lowest set bit (bit 1 thấp nhất)
    int low = mask & (-mask); // 1 (bit 0)

    // Clear lowest set bit
    int cleared = mask & (mask - 1); // 1100₂

    // Đếm số bit 1 (kích thước tập)
    int cnt = __builtin_popcount(mask); // 3

    printf("mask=%d, has2=%d, low=%d, cleared=%d, cnt=%d\n",
           mask, has2, low, cleared, cnt);
    return 0;
}

python

mask = 0b1010  # tập {1, 3}

# Set bit i (thêm phần tử i vào tập)
mask |= (1 << 2)   # mask = 0b1110 = {1, 2, 3}

# Clear bit i (xoá phần tử i khỏi tập)
mask &= ~(1 << 1)  # mask = 0b1100 = {2, 3}

# Toggle bit i (đảo trạng thái phần tử i)
mask ^= (1 << 0)   # mask = 0b1101 = {0, 2, 3}

# Check bit i (phần tử i có trong tập?)
has2 = (mask >> 2) & 1  # 1 (True)

# Lowest set bit (bit 1 thấp nhất)
low = mask & (-mask)  # 1 (bit 0)

# Clear lowest set bit
cleared = mask & (mask - 1)  # 0b1100

# Đếm số bit 1 (kích thước tập)
cnt = bin(mask).count('1')  # 3

print(f"mask={mask}, has2={has2}, low={low}, cleared={cleared}, cnt={cnt}")

java

public class BitmaskBasics {
    public static void main(String[] args) {
        int mask = 0b1010; // tập {1, 3}

        // Set bit i (thêm phần tử i vào tập)
        mask |= (1 << 2);   // mask = 0b1110 = {1, 2, 3}

        // Clear bit i (xoá phần tử i khỏi tập)
        mask &= ~(1 << 1);  // mask = 0b1100 = {2, 3}

        // Toggle bit i (đảo trạng thái phần tử i)
        mask ^= (1 << 0);   // mask = 0b1101 = {0, 2, 3}

        // Check bit i (phần tử i có trong tập?)
        boolean has2 = ((mask >> 2) & 1) == 1; // true

        // Lowest set bit (bit 1 thấp nhất)
        int low = mask & (-mask); // 1 (bit 0)

        // Clear lowest set bit
        int cleared = mask & (mask - 1); // 0b1100

        // Đếm số bit 1 (kích thước tập)
        int cnt = Integer.bitCount(mask); // 3

        System.out.printf("mask=%d, has2=%b, low=%d, cleared=%d, cnt=%d%n",
                          mask, has2, low, cleared, cnt);
    }
}

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	mask := 0b1010 // tập {1, 3}

	// Set bit i (thêm phần tử i vào tập)
	mask |= (1 << 2) // mask = 0b1110 = {1, 2, 3}

	// Clear bit i (xoá phần tử i khỏi tập)
	mask &= ^(1 << 1) // mask = 0b1100 = {2, 3}

	// Toggle bit i (đảo trạng thái phần tử i)
	mask ^= (1 << 0) // mask = 0b1101 = {0, 2, 3}

	// Check bit i (phần tử i có trong tập?)
	has2 := (mask>>2)&1 == 1 // true

	// Lowest set bit (bit 1 thấp nhất)
	low := mask & (-mask) // 1 (bit 0)

	// Clear lowest set bit
	cleared := mask & (mask - 1) // 0b1100

	// Đếm số bit 1 (kích thước tập)
	cnt := bits.OnesCount(uint(mask)) // 3

	fmt.Printf("mask=%d, has2=%v, low=%d, cleared=%d, cnt=%d\n",
		mask, has2, low, cleared, cnt)
}

Liệt kê tất cả tập con (Subset Enumeration)

Với N phần tử, ta duyệt tất cả 2^N tập con bằng cách lặp mask từ 0 đến 2^N - 1. Mỗi giá trị mask biểu diễn đúng một tập con.

C++PythonJavaGo

cpp

#include <cstdio>
#include <vector>
using namespace std;

void enumerateSubsets(int n) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        printf("{");
        bool first = true;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                if (!first) printf(", ");
                printf("%d", i);
                first = false;
            }
        }
        printf("}\n");
    }
}

int main() {
    // Liệt kê tất cả tập con của {0, 1, 2, 3}
    enumerateSubsets(4); // 16 tập con
    return 0;
}

python

def enumerate_subsets(n: int) -> list[list[int]]:
    """Liệt kê tất cả 2^N tập con của {0, 1, ..., n-1}."""
    result = []
    for mask in range(1 << n):
        subset = [i for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

for s in enumerate_subsets(4):
    print(s)

java

import java.util.ArrayList;
import java.util.List;

public class SubsetEnum {
    public static List<List<Integer>> enumerateSubsets(int n) {
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(i);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        for (List<Integer> s : enumerateSubsets(4)) {
            System.out.println(s);
        }
    }
}

package main

import "fmt"

func enumerateSubsets(n int) [][]int {
	var result [][]int
	for mask := 0; mask < (1 << n); mask++ {
		var subset []int
		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 {
				subset = append(subset, i)
			}
		}
		result = append(result, subset)
	}
	return result
}

func main() {
	for _, s := range enumerateSubsets(4) {
		fmt.Println(s)
	}
}

Liệt kê tập con của một mask (Submask Enumeration)

Cho một mask m, ta muốn duyệt tất cả tập con s sao cho s ⊆ m (tức s & m == s). Kỹ thuật kinh điển: bắt đầu từ s = m, lặp s = (s - 1) & m cho đến khi s = 0.

Tổng chi phí duyệt submask cho tất cả mask từ 0 đến 2^N - 1 là O(3^N) (mỗi bit có 3 trạng thái: không thuộc mask, thuộc mask nhưng không thuộc submask, thuộc cả hai).

C++PythonJavaGo

cpp

#include <cstdio>
#include <vector>
using namespace std;

vector<int> enumSubmasks(int mask) {
    vector<int> result;
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        result.push_back(sub);
    }
    result.push_back(0); // tập rỗng
    return result;
}

int main() {
    int mask = 0b1011; // {0, 1, 3}
    printf("Submasks of %d (0b1011):\n", mask);
    for (int s : enumSubmasks(mask)) {
        printf("  %d\n", s);
    }
    // Output: 11, 10, 9, 8, 3, 2, 1, 0
    return 0;
}

python

def enum_submasks(mask: int) -> list[int]:
    """Liệt kê tất cả tập con của mask, bao gồm tập rỗng."""
    result = []
    sub = mask
    while sub > 0:
        result.append(sub)
        sub = (sub - 1) & mask
    result.append(0)
    return result

mask = 0b1011  # {0, 1, 3}
print(f"Submasks of {mask} (0b1011):")
for s in enum_submasks(mask):
    print(f"  {s} = {bin(s)}")

java

import java.util.ArrayList;
import java.util.List;

public class SubmaskEnum {
    public static List<Integer> enumSubmasks(int mask) {
        List<Integer> result = new ArrayList<>();
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            result.add(sub);
        }
        result.add(0);
        return result;
    }

    public static void main(String[] args) {
        int mask = 0b1011; // {0, 1, 3}
        System.out.println("Submasks of " + mask + ":");
        for (int s : enumSubmasks(mask)) {
            System.out.println("  " + s + " = " + Integer.toBinaryString(s));
        }
    }
}

package main

import "fmt"

func enumSubmasks(mask int) []int {
	var result []int
	for sub := mask; sub > 0; sub = (sub - 1) & mask {
		result = append(result, sub)
	}
	result = append(result, 0)
	return result
}

func main() {
	mask := 0b1011 // {0, 1, 3}
	fmt.Printf("Submasks of %d (0b1011):\n", mask)
	for _, s := range enumSubmasks(mask) {
		fmt.Printf("  %d = %b\n", s, s)
	}
}

Gosper's Hack — Liệt kê tổ hợp C(N, K) bằng bitmask

Gosper's hack sinh ra mask tiếp theo có cùng số bit 1 theo thứ tự tăng dần. Ứng dụng: duyệt tất cả tổ hợp C(N, K) mà không cần đệ quy.

Nguyên lý: Cho mask hiện tại, tìm bit 1 thấp nhất c, cộng c vào mask để "carry" lên → phần cao thay đổi đúng cách, phần thấp được reset và dồn bit về phải.

Ví dụ: N=5, K=3 — liệt kê tất cả mask 5-bit có đúng 3 bit 1

00111 → 01011 → 01101 → 01110 → 10011 → 10101 → 10110 → 11001 → 11010 → 11100
  7       11      13      14      19      21      22      25      26      28

C++PythonJavaGo

cpp

#include <cstdio>
#include <vector>
using namespace std;

vector<int> gosperHack(int n, int k) {
    vector<int> result;
    if (k == 0) { result.push_back(0); return result; }
    if (k > n)  return result;

    int mask = (1 << k) - 1;      // K bit thấp nhất bật
    int limit = 1 << n;

    while (mask < limit) {
        result.push_back(mask);
        int c = mask & (-mask);    // bit 1 thấp nhất
        int r = mask + c;          // carry lên
        // Dồn các bit thấp về phải
        mask = (((r ^ mask) >> 2) / c) | r;
    }
    return result;
}

int main() {
    // C(5, 3) = 10 tổ hợp
    auto combos = gosperHack(5, 3);
    printf("C(5,3) = %zu combinations:\n", combos.size());
    for (int m : combos) {
        printf("  %2d = ", m);
        for (int i = 4; i >= 0; --i) printf("%d", (m >> i) & 1);
        printf("\n");
    }
    return 0;
}

python

def gosper_hack(n: int, k: int) -> list[int]:
    """Sinh tất cả mask n-bit có đúng k bit 1 (Gosper's hack)."""
    if k == 0:
        return [0]
    if k > n:
        return []

    result = []
    mask = (1 << k) - 1  # K bit thấp nhất bật
    limit = 1 << n

    while mask < limit:
        result.append(mask)
        c = mask & (-mask)           # bit 1 thấp nhất
        r = mask + c                 # carry lên
        mask = (((r ^ mask) >> 2) // c) | r
    return result

# C(5, 3) = 10 tổ hợp
combos = gosper_hack(5, 3)
print(f"C(5,3) = {len(combos)} combinations:")
for m in combos:
    print(f"  {m:2d} = {m:05b}")

java

import java.util.ArrayList;
import java.util.List;

public class GosperHack {
    public static List<Integer> gosperHack(int n, int k) {
        List<Integer> result = new ArrayList<>();
        if (k == 0) { result.add(0); return result; }
        if (k > n) return result;

        int mask = (1 << k) - 1;
        int limit = 1 << n;

        while (mask < limit) {
            result.add(mask);
            int c = mask & (-mask);
            int r = mask + c;
            mask = (((r ^ mask) >> 2) / c) | r;
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> combos = gosperHack(5, 3);
        System.out.printf("C(5,3) = %d combinations:%n", combos.size());
        for (int m : combos) {
            System.out.printf("  %2d = %5s%n", m,
                String.format("%5s", Integer.toBinaryString(m))
                      .replace(' ', '0'));
        }
    }
}

package main

import "fmt"

func gosperHack(n, k int) []int {
	if k == 0 {
		return []int{0}
	}
	if k > n {
		return nil
	}

	var result []int
	mask := (1 << k) - 1
	limit := 1 << n

	for mask < limit {
		result = append(result, mask)
		c := mask & (-mask)
		r := mask + c
		mask = (((r ^ mask) >> 2) / c) | r
	}
	return result
}

func main() {
	combos := gosperHack(5, 3)
	fmt.Printf("C(5,3) = %d combinations:\n", len(combos))
	for _, m := range combos {
		fmt.Printf("  %2d = %05b\n", m, m)
	}
}

Thực chiến

Scenario 1: Bài toán TSP với Bitmask DP

Traveling Salesman Problem: Cho N thành phố và ma trận chi phí di chuyển, tìm hành trình ngắn nhất thăm tất cả thành phố đúng một lần rồi quay về điểm xuất phát.

Trạng thái DP: dp[mask][i] = chi phí nhỏ nhất để đến thành phố i, đã thăm đúng tập thành phố biểu diễn bởi mask.

Chuyển trạng thái: Từ dp[mask][last], thử mở rộng sang thành phố next chưa thuộc mask:

dp[mask | (1 << next)][next] = min(dp[mask | (1 << next)][next],
                                    dp[mask][last] + dist[last][next])

Kết quả: min(dp[(1<<N)-1][i] + dist[i][0]) với mọi i.

C++PythonJavaGo

cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20;
const int INF = 1e9;
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

int tspBitmask(int n) {
    memset(dp, 0x3f, sizeof(dp)); // khởi tạo INF
    dp[1][0] = 0; // xuất phát từ thành phố 0

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int last = 0; last < n; ++last) {
            if (!(mask & (1 << last))) continue;
            if (dp[mask][last] >= INF) continue;

            for (int next = 0; next < n; ++next) {
                if (mask & (1 << next)) continue;
                int newMask = mask | (1 << next);
                dp[newMask][next] = min(dp[newMask][next],
                                        dp[mask][last] + dist[last][next]);
            }
        }
    }

    int fullMask = (1 << n) - 1;
    int ans = INF;
    for (int last = 0; last < n; ++last) {
        if (dp[fullMask][last] < INF) {
            ans = min(ans, dp[fullMask][last] + dist[last][0]);
        }
    }
    return ans >= INF ? -1 : ans;
}

int main() {
    int n = 4;
    int d[4][4] = {
        {0, 10, 15, 20},
        {10,  0, 35, 25},
        {15, 35,  0, 30},
        {20, 25, 30,  0}
    };
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = d[i][j];

    printf("Chi phí TSP tối thiểu: %d\n", tspBitmask(n)); // 80
    return 0;
}

python

import sys

def tsp_bitmask(dist: list[list[int]]) -> int:
    """TSP bằng Bitmask DP. Time: O(N² × 2^N), Space: O(N × 2^N)."""
    n = len(dist)
    INF = sys.maxsize

    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # xuất phát từ thành phố 0

    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            if dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                new_mask = mask | (1 << nxt)
                cost = dp[mask][last] + dist[last][nxt]
                if cost < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = cost

    full_mask = (1 << n) - 1
    ans = INF
    for last in range(n):
        if dp[full_mask][last] < INF:
            ans = min(ans, dp[full_mask][last] + dist[last][0])
    return ans if ans < INF else -1

dist = [
    [0, 10, 15, 20],
    [10,  0, 35, 25],
    [15, 35,  0, 30],
    [20, 25, 30,  0],
]
print(f"Chi phí TSP tối thiểu: {tsp_bitmask(dist)}")  # 80

java

import java.util.Arrays;

public class TSPBitmask {
    static final int INF = (int) 1e9;

    public static int tspBitmask(int[][] dist) {
        int n = dist.length;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[1][0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                if (dp[mask][last] >= INF) continue;
                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;
                    int newMask = mask | (1 << next);
                    dp[newMask][next] = Math.min(dp[newMask][next],
                        dp[mask][last] + dist[last][next]);
                }
            }
        }

        int fullMask = (1 << n) - 1;
        int ans = INF;
        for (int last = 0; last < n; last++) {
            if (dp[fullMask][last] < INF) {
                ans = Math.min(ans, dp[fullMask][last] + dist[last][0]);
            }
        }
        return ans >= INF ? -1 : ans;
    }

    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20},
            {10,  0, 35, 25},
            {15, 35,  0, 30},
            {20, 25, 30,  0}
        };
        System.out.printf("Chi phí TSP tối thiểu: %d%n", tspBitmask(dist));
    }
}

package main

import (
	"fmt"
	"math"
)

func tspBitmask(dist [][]int) int {
	n := len(dist)
	INF := math.MaxInt32
	dp := make([][]int, 1<<n)
	for i := range dp {
		dp[i] = make([]int, n)
		for j := range dp[i] {
			dp[i][j] = INF
		}
	}
	dp[1][0] = 0

	for mask := 1; mask < (1 << n); mask++ {
		for last := 0; last < n; last++ {
			if mask&(1<<last) == 0 || dp[mask][last] >= INF {
				continue
			}
			for next := 0; next < n; next++ {
				if mask&(1<<next) != 0 {
					continue
				}
				newMask := mask | (1 << next)
				cost := dp[mask][last] + dist[last][next]
				if cost < dp[newMask][next] {
					dp[newMask][next] = cost
				}
			}
		}
	}

	fullMask := (1 << n) - 1
	ans := INF
	for last := 0; last < n; last++ {
		if dp[fullMask][last] < INF {
			c := dp[fullMask][last] + dist[last][0]
			if c < ans {
				ans = c
			}
		}
	}
	if ans >= INF {
		return -1
	}
	return ans
}

func main() {
	dist := [][]int{
		{0, 10, 15, 20},
		{10, 0, 35, 25},
		{15, 35, 0, 30},
		{20, 25, 30, 0},
	}
	fmt.Printf("Chi phí TSP tối thiểu: %d\n", tspBitmask(dist)) // 80
}

Scenario 2: Hệ thống phân quyền bitwise (Permission System)

Trong hệ thống thực tế, mỗi quyền là một lũy thừa của 2 — tức một bit riêng biệt. Tổ hợp quyền của user là phép OR các bit. Kiểm tra quyền là phép AND.

C++PythonJavaGo

cpp

#include <cstdio>
#include <cstdint>
#include <string>
using namespace std;

// Mỗi quyền chiếm đúng một bit
enum Permission : uint32_t {
    PERM_NONE    = 0,
    PERM_READ    = 1 << 0,  // 1
    PERM_WRITE   = 1 << 1,  // 2
    PERM_DELETE  = 1 << 2,  // 4
    PERM_ADMIN   = 1 << 3,  // 8
    PERM_EXPORT  = 1 << 4,  // 16
    PERM_AUDIT   = 1 << 5,  // 32
};

// Các role được tạo bằng tổ hợp OR
const uint32_t ROLE_VIEWER  = PERM_READ;
const uint32_t ROLE_EDITOR  = PERM_READ | PERM_WRITE;
const uint32_t ROLE_MANAGER = PERM_READ | PERM_WRITE | PERM_DELETE | PERM_EXPORT;
const uint32_t ROLE_ADMIN   = PERM_READ | PERM_WRITE | PERM_DELETE | PERM_ADMIN
                             | PERM_EXPORT | PERM_AUDIT;

bool hasAll(uint32_t userPerms, uint32_t required) {
    return (userPerms & required) == required;
}

bool hasAny(uint32_t userPerms, uint32_t required) {
    return (userPerms & required) != 0;
}

uint32_t grant(uint32_t perms, uint32_t perm)  { return perms | perm; }
uint32_t revoke(uint32_t perms, uint32_t perm) { return perms & ~perm; }
uint32_t toggle(uint32_t perms, uint32_t perm) { return perms ^ perm; }

int main() {
    uint32_t user = ROLE_EDITOR; // READ | WRITE = 3
    printf("hasAll(READ|WRITE)? %d\n", hasAll(user, PERM_READ | PERM_WRITE));
    printf("hasAll(DELETE)?     %d\n", hasAll(user, PERM_DELETE));
    printf("hasAny(DELETE|ADMIN)? %d\n", hasAny(user, PERM_DELETE | PERM_ADMIN));

    user = grant(user, PERM_ADMIN);
    printf("Sau grant ADMIN: %u\n", user);

    user = revoke(user, PERM_WRITE);
    printf("Sau revoke WRITE: %u\n", user);
    return 0;
}

python

from enum import IntFlag, auto

class Permission(IntFlag):
    NONE   = 0
    READ   = auto()   # 1
    WRITE  = auto()   # 2
    DELETE = auto()   # 4
    ADMIN  = auto()   # 8
    EXPORT = auto()   # 16
    AUDIT  = auto()   # 32

# Tạo role bằng tổ hợp OR
ROLE_VIEWER  = Permission.READ
ROLE_EDITOR  = Permission.READ | Permission.WRITE
ROLE_MANAGER = Permission.READ | Permission.WRITE | Permission.DELETE | Permission.EXPORT
ROLE_ADMIN   = Permission.READ | Permission.WRITE | Permission.DELETE \
             | Permission.ADMIN | Permission.EXPORT | Permission.AUDIT

def has_all(user_perms: int, required: int) -> bool:
    return (user_perms & required) == required

def has_any(user_perms: int, required: int) -> bool:
    return (user_perms & required) != 0

def grant(perms: int, perm: int) -> int:
    return perms | perm

def revoke(perms: int, perm: int) -> int:
    return perms & ~perm

user = ROLE_EDITOR  # READ | WRITE = 3
print(f"has_all(READ|WRITE)? {has_all(user, Permission.READ | Permission.WRITE)}")
print(f"has_all(DELETE)?     {has_all(user, Permission.DELETE)}")

user = grant(user, Permission.ADMIN)
print(f"Sau grant ADMIN: {user}")  # READ|WRITE|ADMIN = 11

user = revoke(user, Permission.WRITE)
print(f"Sau revoke WRITE: {user}")  # READ|ADMIN = 9

java

public class PermissionSystem {
    static final int PERM_NONE   = 0;
    static final int PERM_READ   = 1 << 0;
    static final int PERM_WRITE  = 1 << 1;
    static final int PERM_DELETE = 1 << 2;
    static final int PERM_ADMIN  = 1 << 3;
    static final int PERM_EXPORT = 1 << 4;
    static final int PERM_AUDIT  = 1 << 5;

    static final int ROLE_VIEWER  = PERM_READ;
    static final int ROLE_EDITOR  = PERM_READ | PERM_WRITE;
    static final int ROLE_MANAGER = PERM_READ | PERM_WRITE | PERM_DELETE | PERM_EXPORT;
    static final int ROLE_ADMIN   = PERM_READ | PERM_WRITE | PERM_DELETE
                                  | PERM_ADMIN | PERM_EXPORT | PERM_AUDIT;

    static boolean hasAll(int userPerms, int required) {
        return (userPerms & required) == required;
    }

    static boolean hasAny(int userPerms, int required) {
        return (userPerms & required) != 0;
    }

    static int grant(int perms, int perm)  { return perms | perm; }
    static int revoke(int perms, int perm) { return perms & ~perm; }

    public static void main(String[] args) {
        int user = ROLE_EDITOR;
        System.out.println("hasAll(READ|WRITE)? " +
            hasAll(user, PERM_READ | PERM_WRITE));
        System.out.println("hasAll(DELETE)? " +
            hasAll(user, PERM_DELETE));

        user = grant(user, PERM_ADMIN);
        System.out.println("Sau grant ADMIN: " + user);

        user = revoke(user, PERM_WRITE);
        System.out.println("Sau revoke WRITE: " + user);
    }
}

package main

import "fmt"

const (
	PermNone   uint32 = 0
	PermRead   uint32 = 1 << iota // 1
	PermWrite                      // 2
	PermDelete                     // 4
	PermAdmin                      // 8
	PermExport                     // 16
	PermAudit                      // 32
)

var (
	RoleViewer  = PermRead
	RoleEditor  = PermRead | PermWrite
	RoleManager = PermRead | PermWrite | PermDelete | PermExport
	RoleAdmin   = PermRead | PermWrite | PermDelete | PermAdmin |
		PermExport | PermAudit
)

func hasAll(userPerms, required uint32) bool {
	return userPerms&required == required
}

func hasAny(userPerms, required uint32) bool {
	return userPerms&required != 0
}

func grant(perms, perm uint32) uint32  { return perms | perm }
func revoke(perms, perm uint32) uint32 { return perms &^ perm }

func main() {
	user := RoleEditor
	fmt.Println("hasAll(READ|WRITE)?", hasAll(user, PermRead|PermWrite))
	fmt.Println("hasAll(DELETE)?", hasAll(user, PermDelete))

	user = grant(user, PermAdmin)
	fmt.Println("Sau grant ADMIN:", user)

	user = revoke(user, PermWrite)
	fmt.Println("Sau revoke WRITE:", user)
}

Sai lầm điển hình

❌ Sai lầm 1: Overflow khi shift trên 32-bit

Trong C++, 1 << 31 trên kiểu int gây undefined behavior vì int là 32-bit có dấu.

cpp

// ❌ SAI — undefined behavior với int 32-bit
int mask = 1 << 31; // overflow!

// ✅ ĐÚNG — dùng 1LL hoặc ép kiểu
long long mask = 1LL << 31;
// Hoặc:
unsigned int mask = 1u << 31;

❌ Sai lầm 2: Quên mask rỗng khi duyệt submask

Vòng lặp for (sub = mask; sub > 0; sub = (sub-1) & mask) bỏ qua tập rỗng (sub = 0).

python

# ❌ SAI — thiếu tập rỗng
sub = mask
while sub > 0:
    process(sub)
    sub = (sub - 1) & mask
# Không xử lý sub = 0!

# ✅ ĐÚNG — thêm xử lý tập rỗng sau vòng lặp
sub = mask
while sub > 0:
    process(sub)
    sub = (sub - 1) & mask
process(0)  # xử lý tập rỗng

❌ Sai lầm 3: Nhầm `&` với `&&` (bitwise vs logical)

Phép & (bitwise AND) và && (logical AND) cho kết quả hoàn toàn khác nhau khi dùng để kiểm tra bit.

cpp

int mask = 6; // 0b110

// ❌ SAI — && trả về 0 hoặc 1, không phải giá trị bit
if (mask && (1 << 1)) { } // luôn true vì mask != 0

// ✅ ĐÚNG — & kiểm tra chính xác bit
if (mask & (1 << 1)) { }  // true vì bit 1 bật
if (mask & (1 << 0)) { }  // false vì bit 0 tắt

❌ Sai lầm 4: Sai index khi ánh xạ bit sang phần tử

Bit 0 tương ứng phần tử index 0, không phải phần tử cuối. Nhầm lẫn thứ tự gây ra kết quả sai âm thầm.

python

arr = ['A', 'B', 'C', 'D']
mask = 0b1010  # bit 1 và bit 3 bật

# ❌ SAI — đọc bit từ trái sang phải như chuỗi nhị phân
# Nghĩ mask = "1010" → phần tử 0 và 2 → ['A', 'C']

# ✅ ĐÚNG — bit i tương ứng arr[i]
# bit 1 = 1 → arr[1] = 'B'
# bit 3 = 1 → arr[3] = 'D'
subset = [arr[i] for i in range(len(arr)) if mask & (1 << i)]
# subset = ['B', 'D']

Under the Hood

Hardware Popcount và Compiler Intrinsics

CPU hiện đại có instruction POPCNT đếm số bit 1 trong một chu kỳ xung nhịp. Các ngôn ngữ cung cấp wrapper:

Ngôn ngữ	Hàm / Intrinsic	Ghi chú
C++ (GCC/Clang)	`__builtin_popcount(x)`	32-bit; dùng `__builtin_popcountll` cho 64-bit
C++ (MSVC)	`__popcnt(x)`	Cần `#include <intrin.h>`
Java	`Integer.bitCount(x)`	Dùng POPCNT nếu JVM hỗ trợ
Python	`bin(x).count('1')`	Không dùng hardware; dùng `x.bit_count()` từ Python 3.10
Go	`bits.OnesCount(x)`	Package `math/bits`, dùng POPCNT trên x86

Các intrinsic hữu ích khác:

Thao tác	C++ (GCC)	Java	Ý nghĩa
Bit 1 thấp nhất (vị trí)	`__builtin_ctz(x)`	`Integer.numberOfTrailingZeros(x)`	Count trailing zeros
Bit 1 cao nhất (vị trí)	`31 - __builtin_clz(x)`	`31 - Integer.numberOfLeadingZeros(x)`	Count leading zeros
Kiểm tra lũy thừa 2	`__builtin_popcount(x) == 1`	`Integer.bitCount(x) == 1`	Hoặc `x & (x-1) == 0`

Bảng phân tích độ phức tạp

Kỹ thuật	Thời gian	Không gian	Ràng buộc N
Liệt kê 2^N tập con	O(N × 2^N)	O(1) nếu chỉ duyệt	N ≤ 25
Duyệt submask của mọi mask	O(3^N) tổng	O(1)	N ≤ 16
Gosper's hack C(N,K)	O(C(N,K))	O(1) nếu chỉ duyệt	N ≤ 25
Bitmask DP (TSP)	O(N² × 2^N)	O(N × 2^N)	N ≤ 20
DP chia submask	O(3^N)	O(2^N)	N ≤ 16

Khi nào Bitmask DP không khả thi?

Ngưỡng cứng: N ≤ 20. Với N = 20, bảng DP có 20 × 2^20 ≈ 20 triệu ô — chấp nhận được. Nhưng N = 25 → 25 × 2^25 ≈ 800 triệu ô → tràn bộ nhớ và quá thời gian.

Khi N > 20, xem xét các phương án thay thế:

Meet in the middle: Chia N thành hai nửa, mỗi nửa ≤ N/2, kết hợp kết quả.
Pruning / Branch and Bound: Cắt tỉa nhánh tìm kiếm.
Heuristic / Approximation: Cho bài toán tối ưu không cần đáp án chính xác.

Checklist ghi nhớ

✅ Checklist triển khai

[ ] Bit thứ i tương ứng phần tử thứ i — đánh số từ 0
[ ] mask | (1 << i) để thêm phần tử, mask & ~(1 << i) để xoá
[ ] (mask >> i) & 1 kiểm tra phần tử thuộc tập — trả về 0 hoặc 1
[ ] mask & (mask - 1) xoá bit 1 thấp nhất — dùng đếm popcount thủ công
[ ] mask & (-mask) trích xuất bit 1 thấp nhất — nền tảng Gosper's hack
[ ] Duyệt submask: for (sub = mask; sub > 0; sub = (sub-1) & mask) — nhớ xử lý sub = 0 riêng
[ ] Tổng chi phí duyệt submask cho mọi mask: O(3^N), không phải O(4^N)
[ ] Gosper's hack sinh mask tiếp theo cùng số bit 1 — dùng cho C(N, K)
[ ] Trong C++: luôn dùng 1LL << k khi k ≥ 31 để tránh undefined behavior
[ ] Bitmask DP khả thi khi N ≤ 20 — vượt ngưỡng cần meet-in-the-middle
[ ] Dùng __builtin_popcount (C++), Integer.bitCount (Java), bits.OnesCount (Go) thay vì đếm thủ công
[ ] Phân quyền bitwise: mỗi quyền = một bit, kiểm tra bằng AND, cấp bằng OR, thu hồi bằng AND NOT
[ ] Kiểm tra hasAll: (perms & required) == required — không phải != 0
[ ] Phân biệt & (bitwise) và && (logical) — lỗi kinh điển trong C/C++/Java

Bài tập luyện tập

Bài 1 (Foundation): Đếm số bit 1 trong một số

Viết hàm countBits(n) đếm số bit 1 trong biểu diễn nhị phân của n không dùng hàm built-in. Yêu cầu: O(k) với k là số bit 1.

🧠 Quiz

Câu hỏi: Phép toán n & (n - 1) có tác dụng gì?

A) Đặt bit thấp nhất thành 1
B) Xoá bit 1 thấp nhất của n
C) Đảo tất cả các bit của n
D) Nhân n với 2

Giải thích: n - 1 đảo bit 1 thấp nhất và tất cả bit 0 bên phải nó. Khi AND với n, bit 1 thấp nhất bị xoá. Đây là nền tảng của thuật toán Brian Kernighan.

💡 Lời giải tham khảo

C++PythonJavaGo

cpp

int countBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // xoá bit 1 thấp nhất
        count++;
    }
    return count;
}

python

def count_bits(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

java

static int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

func countBits(n int) int {
    count := 0
    for n != 0 {
        n &= (n - 1)
        count++
    }
    return count
}

Thuật toán Brian Kernighan: Mỗi lần n &= (n-1) xoá đúng một bit 1. Vòng lặp chạy đúng k lần với k = số bit 1. Độ phức tạp: O(k) thay vì O(log n) nếu duyệt từng bit.

Bài 2 (Intermediate): Liệt kê tất cả tập con có đúng K phần tử

Cho mảng arr có N phần tử (N ≤ 20) và số nguyên K, liệt kê tất cả tập con có đúng K phần tử. Dùng Gosper's hack.

🧠 Quiz

Câu hỏi: Gosper's hack sinh mask tiếp theo có cùng số bit 1. Nếu mask hiện tại là 01110 (14), mask tiếp theo là gì?

A) 10001 (17)
B) 10011 (19)
C) 10101 (21)
D) 11100 (28)

Giải thích: Từ 01110: bit 1 thấp nhất ở vị trí 1, c = 2. r = 14 + 2 = 16 = 10000. ((r ^ mask) >> 2) / c = ((10000 ^ 01110) >> 2) / 2 = (11110 >> 2) / 2 = 00111 / 2 = 00011. Kết quả: 00011 | 10000 = 10011 = 19.

💡 Lời giải tham khảo

C++PythonJavaGo

cpp

#include <cstdio>
#include <vector>
using namespace std;

void printKSubsets(int arr[], int n, int k) {
    if (k == 0) { printf("{}\n"); return; }
    if (k > n) return;

    int mask = (1 << k) - 1;
    int limit = 1 << n;

    while (mask < limit) {
        printf("{");
        bool first = true;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                if (!first) printf(", ");
                printf("%d", arr[i]);
                first = false;
            }
        }
        printf("}\n");

        int c = mask & (-mask);
        int r = mask + c;
        mask = (((r ^ mask) >> 2) / c) | r;
    }
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    printKSubsets(arr, 5, 3);
    return 0;
}

python

def k_subsets(arr: list, k: int) -> list[list]:
    n = len(arr)
    if k == 0:
        return [[]]
    if k > n:
        return []

    result = []
    mask = (1 << k) - 1
    limit = 1 << n

    while mask < limit:
        subset = [arr[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
        c = mask & (-mask)
        r = mask + c
        mask = (((r ^ mask) >> 2) // c) | r
    return result

for s in k_subsets([10, 20, 30, 40, 50], 3):
    print(s)

java

import java.util.ArrayList;
import java.util.List;

public class KSubsets {
    public static List<List<Integer>> kSubsets(int[] arr, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int n = arr.length;
        if (k == 0) { result.add(new ArrayList<>()); return result; }
        if (k > n) return result;

        int mask = (1 << k) - 1;
        int limit = 1 << n;

        while (mask < limit) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) subset.add(arr[i]);
            }
            result.add(subset);
            int c = mask & (-mask);
            int r = mask + c;
            mask = (((r ^ mask) >> 2) / c) | r;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        for (List<Integer> s : kSubsets(arr, 3)) {
            System.out.println(s);
        }
    }
}

package main

import "fmt"

func kSubsets(arr []int, k int) [][]int {
	n := len(arr)
	if k == 0 {
		return [][]int{{}}
	}
	if k > n {
		return nil
	}

	var result [][]int
	mask := (1 << k) - 1
	limit := 1 << n

	for mask < limit {
		var subset []int
		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 {
				subset = append(subset, arr[i])
			}
		}
		result = append(result, subset)
		c := mask & (-mask)
		r := mask + c
		mask = (((r ^ mask) >> 2) / c) | r
	}
	return result
}

func main() {
	arr := []int{10, 20, 30, 40, 50}
	for _, s := range kSubsets(arr, 3) {
		fmt.Println(s)
	}
}

🧠 Quiz

Câu hỏi: Tổng chi phí duyệt submask cho TẤT CẢ mask từ 0 đến 2^N - 1 là bao nhiêu?

A) O(2^N)
B) O(N × 2^N)
C) O(3^N)
D) O(4^N)

Giải thích: Mỗi phần tử thuộc vào đúng 1 trong 3 trạng thái: (1) không thuộc mask ngoài, (2) thuộc mask ngoài nhưng không thuộc submask, (3) thuộc cả mask ngoài lẫn submask. Với N phần tử, tổng số cặp (mask, submask) là 3^N.

Bitmasking — Nghệ thuật nén tập hợp vào số nguyên ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Các phép toán bitmask cơ bản ​

Liệt kê tất cả tập con (Subset Enumeration) ​

Liệt kê tập con của một mask (Submask Enumeration) ​

Gosper's Hack — Liệt kê tổ hợp C(N, K) bằng bitmask ​

Thực chiến ​

Scenario 1: Bài toán TSP với Bitmask DP ​

Scenario 2: Hệ thống phân quyền bitwise (Permission System) ​

Sai lầm điển hình ​

❌ Sai lầm 1: Overflow khi shift trên 32-bit ​

❌ Sai lầm 2: Quên mask rỗng khi duyệt submask ​

❌ Sai lầm 3: Nhầm & với && (bitwise vs logical) ​

❌ Sai lầm 4: Sai index khi ánh xạ bit sang phần tử ​

Under the Hood ​

Hardware Popcount và Compiler Intrinsics ​

Bảng phân tích độ phức tạp ​

Khi nào Bitmask DP không khả thi? ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1 (Foundation): Đếm số bit 1 trong một số ​

Bài 2 (Intermediate): Liệt kê tất cả tập con có đúng K phần tử ​

Liên kết học tiếp ​

Bitmasking — Nghệ thuật nén tập hợp vào số nguyên

Bức tranh tư duy

Cốt lõi kỹ thuật

Các phép toán bitmask cơ bản

Liệt kê tất cả tập con (Subset Enumeration)

Liệt kê tập con của một mask (Submask Enumeration)

Gosper's Hack — Liệt kê tổ hợp C(N, K) bằng bitmask

Thực chiến

Scenario 1: Bài toán TSP với Bitmask DP

Scenario 2: Hệ thống phân quyền bitwise (Permission System)

Sai lầm điển hình

❌ Sai lầm 1: Overflow khi shift trên 32-bit

❌ Sai lầm 2: Quên mask rỗng khi duyệt submask

❌ Sai lầm 3: Nhầm `&` với `&&` (bitwise vs logical)

❌ Sai lầm 4: Sai index khi ánh xạ bit sang phần tử

Under the Hood

Hardware Popcount và Compiler Intrinsics

Bảng phân tích độ phức tạp

Khi nào Bitmask DP không khả thi?

Checklist ghi nhớ

Bài tập luyện tập

Bài 1 (Foundation): Đếm số bit 1 trong một số

Bài 2 (Intermediate): Liệt kê tất cả tập con có đúng K phần tử

Liên kết học tiếp