Giao diện
Bitmasking - Subset & Permission Magic
"1 integer = 32 booleans. Bitmasking tiết kiệm memory 32x và nhanh hơn 100x." - HPN
What is Bitmasking?
Bitmasking = Dùng các bit của một số nguyên để represent một tập hợp hoặc trạng thái.
Integer 13 = 0b1101
Bit positions: 3 2 1 0
Bit values: 1 1 0 1
→ Set contains: {0, 2, 3}
→ Features enabled: Feature0, Feature2, Feature3Application 1: Subset Generation
Generate All Subsets
python
def generate_subsets(arr: list) -> list:
"""
Generate all 2^N subsets of array.
Time: O(N × 2^N)
Space: O(2^N)
How it works:
- Each subset corresponds to a bitmask from 0 to 2^N - 1
- Bit i = 1 means include arr[i]
Example: arr = [a, b, c]
mask = 5 = 0b101 → include arr[0] and arr[2] → [a, c]
"""
n = len(arr)
subsets = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # Check if bit i is set
subset.append(arr[i])
subsets.append(subset)
return subsets
# Demo
arr = ['a', 'b', 'c']
subsets = generate_subsets(arr)
print(f"All {len(subsets)} subsets of {arr}:")
for s in subsets:
print(f" {s}")Iterate Over Subsets of a Mask
python
def iterate_submasks(mask: int):
"""
Iterate over all submasks of a given mask.
Example: mask = 0b1011 (11)
Submasks: 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
Time: O(2^k) where k = number of set bits
"""
submask = mask
while submask > 0:
yield submask
submask = (submask - 1) & mask
yield 0 # Include empty set
# Demo
mask = 0b1011
print(f"Submasks of {bin(mask)}:")
for sub in iterate_submasks(mask):
print(f" {bin(sub)}")Application 2: Permission Systems (RBAC)
Bitwise Permissions
python
from enum import IntFlag, auto
from typing import Set
class Permission(IntFlag):
"""
Bitwise permissions using IntFlag.
Each permission is a power of 2 → Single bit.
Combine with OR, check with AND.
"""
NONE = 0
READ = auto() # 1
WRITE = auto() # 2
DELETE = auto() # 4
ADMIN = auto() # 8
# Composite permissions
READ_WRITE = READ | WRITE
ALL = READ | WRITE | DELETE | ADMIN
def has_permission(user_perms: int, required: int) -> bool:
"""Check if user has ALL required permissions."""
return (user_perms & required) == required
def has_any_permission(user_perms: int, required: int) -> bool:
"""Check if user has ANY of required permissions."""
return (user_perms & required) != 0
def grant_permission(user_perms: int, perm: int) -> int:
"""Grant permission to user."""
return user_perms | perm
def revoke_permission(user_perms: int, perm: int) -> int:
"""Revoke permission from user."""
return user_perms & ~perm
def toggle_permission(user_perms: int, perm: int) -> int:
"""Toggle permission on/off."""
return user_perms ^ perm
# Demo
user = Permission.READ | Permission.WRITE # 3 = 0b11
print(f"User permissions: {user}")
print(f"Has READ? {has_permission(user, Permission.READ)}") # True
print(f"Has DELETE? {has_permission(user, Permission.DELETE)}") # False
print(f"Has READ or ADMIN? {has_any_permission(user, Permission.READ | Permission.ADMIN)}") # True
user = grant_permission(user, Permission.ADMIN)
print(f"After granting ADMIN: {user}") # READ|WRITE|ADMIN
user = revoke_permission(user, Permission.WRITE)
print(f"After revoking WRITE: {user}") # READ|ADMINReal-World: Unix File Permissions
python
class UnixPermission:
"""
Unix-like rwx permissions.
Each digit = 3 bits:
- Read (4)
- Write (2)
- Execute (1)
Example: 755 = rwxr-xr-x
- Owner: 7 = 111 = rwx
- Group: 5 = 101 = r-x
- Other: 5 = 101 = r-x
"""
READ = 4
WRITE = 2
EXECUTE = 1
@staticmethod
def from_octal(octal_str: str) -> tuple:
"""Parse '755' → (owner, group, other) permissions."""
digits = [int(d) for d in octal_str]
return tuple(digits)
@staticmethod
def to_string(perm: int) -> str:
"""Convert 7 → 'rwx', 5 → 'r-x'."""
r = 'r' if perm & 4 else '-'
w = 'w' if perm & 2 else '-'
x = 'x' if perm & 1 else '-'
return r + w + x
@staticmethod
def format_permissions(octal_str: str) -> str:
"""Convert '755' → 'rwxr-xr-x'."""
perms = UnixPermission.from_octal(octal_str)
return ''.join(UnixPermission.to_string(p) for p in perms)
# Demo
print(f"755 = {UnixPermission.format_permissions('755')}") # rwxr-xr-x
print(f"644 = {UnixPermission.format_permissions('644')}") # rw-r--r--
print(f"777 = {UnixPermission.format_permissions('777')}") # rwxrwxrwxApplication 3: DP State Compression
Traveling Salesman (TSP) với Bitmask DP
python
from typing import List
import sys
def tsp_bitmask(dist: List[List[int]]) -> int:
"""
Traveling Salesman Problem using Bitmask DP.
Find minimum cost to visit all cities exactly once
and return to starting city.
Time: O(N² × 2^N)
Space: O(N × 2^N)
State: dp[mask][i] = min cost to visit cities in mask, ending at i
"""
n = len(dist)
INF = sys.maxsize
# dp[mask][i] = min cost to reach city i, having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # Start at city 0, only city 0 visited
for mask in range(1, 1 << n):
for last in range(n):
if not (mask & (1 << last)):
continue # City 'last' not in mask
if dp[mask][last] == INF:
continue
for next_city in range(n):
if mask & (1 << next_city):
continue # Already visited
new_mask = mask | (1 << next_city)
dp[new_mask][next_city] = min(
dp[new_mask][next_city],
dp[mask][last] + dist[last][next_city]
)
# Return to starting city
full_mask = (1 << n) - 1
result = INF
for last in range(n):
if dp[full_mask][last] != INF:
result = min(result, dp[full_mask][last] + dist[last][0])
return result if result != INF else -1
# Demo
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
print(f"TSP minimum cost: {tsp_bitmask(dist)}") # 80Production Code
python
# HPN Engineering Standard
# Implementation: Bitmasking Utilities
from typing import List, Set, Iterator, TypeVar
from dataclasses import dataclass
T = TypeVar('T')
class Bitmask:
"""Utility class for bitmask operations."""
@staticmethod
def from_set(indices: Set[int]) -> int:
"""Create bitmask from set of indices."""
mask = 0
for i in indices:
mask |= (1 << i)
return mask
@staticmethod
def to_set(mask: int) -> Set[int]:
"""Convert bitmask to set of indices."""
result = set()
i = 0
while mask:
if mask & 1:
result.add(i)
mask >>= 1
i += 1
return result
@staticmethod
def count_bits(mask: int) -> int:
"""Count number of set bits (popcount)."""
count = 0
while mask:
count += 1
mask &= (mask - 1)
return count
@staticmethod
def lowest_bit(mask: int) -> int:
"""Get lowest set bit."""
return mask & (-mask)
@staticmethod
def highest_bit(mask: int) -> int:
"""Get highest set bit position."""
if mask == 0:
return -1
pos = 0
while mask:
mask >>= 1
pos += 1
return pos - 1
@staticmethod
def all_subsets(mask: int) -> Iterator[int]:
"""Iterate all subsets of mask."""
sub = mask
while sub > 0:
yield sub
sub = (sub - 1) & mask
yield 0
@staticmethod
def generate_combinations(n: int, k: int) -> Iterator[int]:
"""Generate all bitmasks with exactly k bits set (n choose k)."""
if k == 0:
yield 0
return
if k > n:
return
mask = (1 << k) - 1
limit = 1 << n
while mask < limit:
yield mask
# Gosper's hack
c = mask & -mask
r = mask + c
mask = (((r ^ mask) >> 2) // c) | r
def subsets_of_array(arr: List[T]) -> List[List[T]]:
"""Generate all subsets of array."""
n = len(arr)
result = []
for mask in range(1 << n):
subset = [arr[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
print("=== Bitmask Utilities ===")
# Set operations
s = {0, 2, 4}
mask = Bitmask.from_set(s)
print(f"Set {s} → mask {bin(mask)} ({mask})")
print(f"Mask {mask} → set {Bitmask.to_set(mask)}")
# Bit counting
print(f"Bits in {bin(0b1011)}: {Bitmask.count_bits(0b1011)}") # 3
# Generate combinations (5 choose 3)
print("\n5 choose 3:")
for mask in Bitmask.generate_combinations(5, 3):
print(f" {bin(mask):>7} → {Bitmask.to_set(mask)}")
# Subsets
print("\n=== Subsets of [A, B, C] ===")
subsets = subsets_of_array(['A', 'B', 'C'])
for s in subsets:
print(f" {s}")
)Bitmasking Cheat Sheet
| Operation | Code | Time |
|---|---|---|
| Set bit i | mask | (1 << i) | O(1) |
| Clear bit i | mask & ~(1 << i) | O(1) |
| Toggle bit i | mask ^ (1 << i) | O(1) |
| Check bit i | (mask >> i) & 1 | O(1) |
| Lowest set bit | mask & (-mask) | O(1) |
| Clear lowest bit | mask & (mask-1) | O(1) |
| Count set bits | Loop or bin(mask).count('1') | O(log mask) |
| All subsets | sub = (sub-1) & mask | O(2^k) |
💡 HPN's Rule
"Subset/Combination với N ≤ 20 → Bitmask DP. N > 20 → 2^N quá lớn, cần approach khác."