2.15 ✅ Thao tác bit (Bit Manipulation)
- Đặc tính của phép XOR. Bài 136, 268, 389, 421.
x ^ 0 = x x ^ 11111……1111 = ~x x ^ (~x) = 11111……1111 x ^ x = 0 a ^ b = c => a ^ c = b => b ^ c = a (Tính giao hoán) a ^ b ^ c = a ^ (b ^ c) = (a ^ b）^ c (Tính kết hợp)
- Xây dựng mask đặc biệt, đặt các vị trí cần thiết thành 0 hoặc 1.
Dọn sạch n bit ngoài cùng bên phải của x: x & ( ~0 << n ) Lấy giá trị bit thứ n của x (0 hoặc 1): (x >> n) & 1 Lấy giá trị lũy thừa ứng với bit thứ n: x & (1 << (n - 1)) Chỉ đặt bit thứ n thành 1: x | (1 << n) Chỉ đặt bit thứ n thành 0: x & (~(1 << n)) Dọn sạch từ bit cao nhất đến bit thứ n (bao gồm n): x & ((1 << n) - 1) Dọn sạch từ bit thứ n đến bit 0 (bao gồm 0): x & (~((1 << (n + 1)) - 1))
- Các phép toán bit AND (&) có ý nghĩa đặc biệt. Bài 260, 201, 318, 371, 397, 461, 693.
X & 1 == 1: kiểm tra số lẻ (chẵn) X &= (X - 1): xoá bit 1 thấp nhất (LSB) X & -X: lấy bit 1 thấp nhất (LSB) X & ~X = 0
| STT | Tiêu đề | Lời giải | Độ khó | Độ phức tạp thời gian | Độ phức tạp bộ nhớ | Yêu thích | Tỷ lệ AC (Acceptance) |
|---|---|---|---|---|---|---|---|
| 0029 | Chia hai số nguyên (Divide Two Integers) | Go | Medium | 17.2% | |||
| 0067 | Cộng nhị phân (Add Binary) | Go | Easy | 52.4% | |||
| 0078 | Các tập con (Subsets) | Go | Medium | O(n^2) | O(n) | ❤️ | 74.9% |
| 0089 | Mã Gray (Gray Code) | Go | Medium | 57.2% | |||
| 0090 | Các tập con II (Subsets II) | Go | Medium | 55.9% | |||
| 0136 | Số duy nhất (Single Number) | Go | Easy | O(n) | O(1) | 70.7% | |
| 0137 | Số duy nhất II (Single Number II) | Go | Medium | O(n) | O(1) | ❤️ | 58.5% |
| 0187 | Các chuỗi DNA lặp lại (Repeated DNA Sequences) | Go | Medium | O(n) | O(1) | 47.0% | |
| 0190 | Đảo bit (Reverse Bits) | Go | Easy | O(n) | O(1) | ❤️ | 54.0% |
| 0191 | Số lượng bit 1 (Number of 1 Bits) | Go | Easy | O(n) | O(1) | 66.6% | |
| 0201 | AND theo bit của đoạn số (Bitwise AND of Numbers Range) | Go | Medium | O(n) | O(1) | ❤️ | 42.5% |
| 0231 | Lũy thừa của 2 (Power of Two) | Go | Easy | O(1) | O(1) | 46.0% | |
| 0260 | Số duy nhất III (Single Number III) | Go | Medium | O(n) | O(1) | ❤️ | 67.7% |
| 0268 | Số bị thiếu (Missing Number) | Go | Easy | O(n) | O(1) | 62.6% | |
| 0287 | Tìm số bị lặp (Find the Duplicate Number) | Go | Medium | 59.1% | |||
| 0318 | Tích lớn nhất của độ dài từ (Maximum Product of Word Lengths) | Go | Medium | O(n) | O(1) | 59.9% | |
| 0338 | Đếm bit (Counting Bits) | Go | Easy | O(n) | O(n) | 75.8% | |
| 0342 | Lũy thừa của 4 (Power of Four) | Go | Easy | O(n) | O(1) | 46.2% | |
| 0371 | Tổng của hai số nguyên (Sum of Two Integers) | Go | Medium | O(n) | O(1) | 50.7% | |
| 0389 | Tìm ký tự khác biệt (Find the Difference) | Go | Easy | O(n) | O(1) | 59.9% | |
| 0393 | Xác thực UTF-8 (UTF-8 Validation) | Go | Medium | O(n) | O(1) | 45.1% | |
| 0397 | Thay thế số nguyên (Integer Replacement) | Go | Medium | O(n) | O(1) | 35.2% | |
| 0401 | Đồng hồ nhị phân (Binary Watch) | Go | Easy | O(1) | O(1) | 52.3% | |
| 0405 | Chuyển số sang hệ thập lục phân (Convert a Number to Hexadecimal) | Go | Easy | O(n) | O(1) | 46.8% | |
| 0421 | XOR lớn nhất của hai số trong mảng (Maximum XOR of Two Numbers in an Array) | Go | Medium | O(n) | O(1) | ❤️ | 54.0% |
| 0461 | Khoảng cách Hamming (Hamming Distance) | Go | Easy | O(n) | O(1) | 75.0% | |
| 0473 | Diêm que tạo hình vuông (Matchsticks to Square) | Go | Medium | 40.2% | |||
| 0476 | Phần bù của số (Number Complement) | Go | Easy | O(n) | O(1) | 67.4% | |
| 0477 | Tổng khoảng cách Hamming (Total Hamming Distance) | Go | Medium | O(n) | O(1) | 52.2% | |
| 0491 | Các dãy con không giảm (Non-decreasing Subsequences) | Go | Medium | 60.2% | |||
| 0526 | Sắp xếp đẹp (Beautiful Arrangement) | Go | Medium | 64.4% | |||
| 0638 | Ưu đãi mua sắm (Shopping Offers) | Go | Medium | 53.3% | |||
| 0645 | Sai lệch tập hợp (Set Mismatch) | Go | Easy | 42.7% | |||
| 0693 | Số nhị phân với bit xen kẽ (Binary Number with Alternating Bits) | Go | Easy | O(n) | O(1) | ❤️ | 61.6% |
| 0756 | Ma trận chuyển tiếp kim tự tháp (Pyramid Transition Matrix) | Go | Medium | O(n log n) | O(n) | 52.7% | |
| 0762 | Số nguyên tố của bit được bật trong biểu diễn nhị phân (Prime Number of Set Bits in Binary Representation) | Go | Easy | O(n) | O(1) | 68.0% | |
| 0784 | Hoán vị chữ hoa/thường (Letter Case Permutation) | Go | Medium | O(n) | O(1) | 73.8% | |
| 0810 | Trò chơi XOR bảng phấn (Chalkboard XOR Game) | Go | Hard | 55.8% | |||
| 0864 | Đường đi ngắn nhất để lấy tất cả chìa khóa (Shortest Path to Get All Keys) | Go | Hard | 45.6% | |||
| 0898 | OR bit của các mảng con (Bitwise ORs of Subarrays) | Go | Medium | O(n) | O(1) | 37.2% | |
| 0980 | Số đường đi duy nhất III (Unique Paths III) | Go | Hard | 81.7% | |||
| 0995 | Số lần lật bit liên tiếp K tối thiểu (Minimum Number of K Consecutive Bit Flips) | Go | Hard | 51.2% | |||
| 0996 | Số lượng mảng squareful (Number of Squareful Arrays) | Go | Hard | 49.2% | |||
| 1009 | Phần bù của số nguyên cơ số 10 (Complement of Base 10 Integer) | Go | Easy | 61.5% | |||
| 1178 | Số từ hợp lệ cho mỗi câu đố (Number of Valid Words for Each Puzzle) | Go | Hard | 46.3% | |||
| 1239 | Độ dài tối đa của chuỗi ghép có ký tự duy nhất (Maximum Length of a Concatenated String with Unique Characters) | Go | Medium | 52.2% | |||
| 1310 | Truy vấn XOR của mảng con (XOR Queries of a Subarray) | Go | Medium | 72.3% | |||
| 1442 | Đếm bộ ba tạo hai mảng có XOR bằng nhau (Count Triplets That Can Form Two Arrays of Equal XOR) | Go | Medium | 76.1% | |||
| 1461 | Kiểm tra chuỗi có chứa tất cả mã nhị phân độ dài K không (Check If a String Contains All Binary Codes of Size K) | Go | Medium | 56.6% | |||
| 1486 | Phép toán XOR trong mảng (XOR Operation in an Array) | Go | Easy | 84.6% | |||
| 1655 | Phân phối số nguyên lặp lại (Distribute Repeating Integers) | Go | Hard | 39.3% | |||
| 1659 | Tối đa hóa hạnh phúc trên lưới (Maximize Grid Happiness) | Go | Hard | 38.8% | |||
| 1680 | Nối các số nhị phân liên tiếp (Concatenation of Consecutive Binary Numbers) | Go | Medium | 57.0% | |||
| 1681 | Độ không tương thích tối thiểu (Minimum Incompatibility) | Go | Hard | 37.8% | |||
| 1684 | Đếm số chuỗi nhất quán (Count the Number of Consistent Strings) | Go | Easy | 82.3% | |||
| 1720 | Giải mã mảng XOR (Decode XORed Array) | Go | Easy | 85.8% | |||
| 1734 | Giải mã hoán vị XOR (Decode XORed Permutation) | Go | Medium | 63.0% | |||
| 1738 | Tìm giá trị tọa độ XOR lớn thứ K (Find Kth Largest XOR Coordinate Value) | Go | Medium | 61.0% | |||
| 1763 | Chuỗi con "nice" dài nhất (Longest Nice Substring) | Go | Easy | 61.5% | |||
| ------------ | ------------------------------------------------------- | ------- | ---------------- | --------------- | ------------- | ------------- | ------------- |