Giao diện
Bit Manipulation Tricks
🎯 Mục tiêu
Luyện tập kiểm tra lũy thừa 2, đếm bit 1, XOR và liệt kê tập con bằng bitmask.
Mô tả bài tập
Thao tác bit giải quyết nhiều bài toán cực kỳ hiệu quả, tối ưu tốc độ lẫn bộ nhớ.
Yêu cầu
Bài 1: Kiểm tra lũy thừa của 2
Kiểm tra một số nguyên dương có phải lũy thừa của 2 mà không dùng vòng lặp.
python
def is_power_of_two(n: int) -> bool:
pass
assert is_power_of_two(16) == True
assert is_power_of_two(18) == False
assert is_power_of_two(1) == True
assert is_power_of_two(0) == FalseBài 2: Đếm số bit 1
Đếm số bit 1 trong biểu diễn nhị phân. Cài đặt naive và Brian Kernighan.
python
def count_bits_naive(n: int) -> int:
pass
def count_bits_kernighan(n: int) -> int:
pass
assert count_bits_naive(13) == 3
assert count_bits_kernighan(255) == 8Bài 3: Thủ thuật XOR
3a. Tìm phần tử xuất hiện 1 lần (các phần tử khác xuất hiện 2 lần).
python
def single_number(nums: list[int]) -> int:
pass
assert single_number([2, 3, 2, 4, 4]) == 33b. Hoán đổi hai số không dùng biến tạm.
python
def swap_without_temp(a: int, b: int) -> tuple[int, int]:
pass
assert swap_without_temp(5, 10) == (10, 5)Bài 4: Liệt kê tập con bằng Bitmask
Cho tập hợp n phần tử, liệt kê tất cả tập con sử dụng bitmask.
python
def enumerate_subsets(elements: list) -> list[list]:
pass
result = enumerate_subsets([1, 2, 3])
assert len(result) == 8
assert [] in result and [1, 2, 3] in resultPhân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 | O(1) | O(1) |
| 2 - Naive | O(log n) | O(1) |
| 2 - Kernighan | O(k) | O(1) |
| 3 | O(n) | O(1) |
| 4 | O(2ⁿ × n) | O(2ⁿ × n) |
Gợi ý
Gợi ý Bài 1
Lũy thừa 2 chỉ có 1 bit 1. Phép AND: n & (n-1) = 0.
Gợi ý Bài 2
Kernighan: & (n-1) xóa bit 1. Lặp đến khi n = 0.
Gợi ý Bài 4
Duyệt mask từ 0 đến 2ⁿ-1. Bit i cho biết phần tử i có trong tập con hay không.
Lời giải tham khảo
Xem lời giải
python
def is_power_of_two(n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0
def count_bits_kernighan(n: int) -> int:
count = 0
while n:
n &= n - 1
count += 1
return count
def single_number(nums: list[int]) -> int:
result = 0
for num in nums: result ^= num
return result
def swap_without_temp(a: int, b: int) -> tuple[int, int]:
a ^= b
b ^= a
a ^= b
return a, b
def enumerate_subsets(elements: list) -> list[list]:
n = len(elements)
subsets = []
for mask in range(1 << n):
subset = [elements[i] for i in range(n) if mask & (1 << i)]
subsets.append(subset)
return subsets