Hướng dẫn giải của Đổi hệ cơ số 16 sang hệ nhị phân
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for hex2bin: Đổi hệ cơ số 16 sang hệ nhị phân
Hiểu bài toán
Bài toán yêu cầu chuyển đổi một số nguyên dương từ hệ cơ số 16 (thập lục phân) sang hệ cơ số 2 (nhị phân). Đầu vào gồm T bộ test, mỗi bộ test là một số thập lục phân (chuỗi ký tự từ '0'-'9' và 'A'-'F'). Số thập lục phân có tối đa 16 ký tự nên giá trị tối đa lên tới $16^{16} - 1$, vượt quá khả năng lưu trữ của kiểu long long (64-bit).
Các cách tiếp cận
Cách Chuyển sang số nguyên rồi chia đôi (Không khả thi)
// Phân tích: Do giới hạn 16 ký tự, số thập lục phân có thể lên tới 16^16 (~1.84e19).
// Kiểu unsigned long long tối đa ~1.84e19, nhưng giá trị tối đa thực tế của 16^16 - 1 là 18,446,744,073,709,551,615.
// Nếu chỉ dùng unsigned long long, ta có thể gặp lỗi tràn số (overflow).
// Tuy nhiên, do giới hạn đề bài $n \le 10^{18}$, nên giá trị thực tế nhỏ hơn $16^{16}$.
// $16^{15} \approx 1.15 \times 10^{18}$.
// Nếu $n \le 10^{18}$, ta có thể dùng unsigned long long.
// Nếu $n$ có thể là $16^{16}$, unsigned long long không đủ.
// Do đó, cách chuyển sang số nguyên không phải là cách tiếp cận an toàn nhất cho mọi test case trong giới hạn đề bài.
- Time Complexity: O(L)
- Space Complexity: O(1)
Cách này chuyển đổi chuỗi thập lục phân thành một số nguyên lớn (big integer hoặc unsigned long long), sau đó chia đôi liên tục để lấy số nhị phân. Tuy nhiên, do giới hạn giá trị $10^{18}$ (thấp hơn $16^{15}$), ta có thể dùng unsigned long long an toàn. Nhưng nếu đề bài sát với $16^{16}$, cách này sẽ sai.
Cách Map từng ký tự sang chuỗi nhị phân 4-bit
#include <stdio.h>
#include <string.h>
int main() {
int t;
scanf("%d", &t);
while (t--) {
char hex[20];
scanf("%s", hex);
int len = strlen(hex);
int started = 0;
for (int i = 0; i < len; i++) {
char c = hex[i];
int val;
if (c >= '0' && c <= '9') val = c - '0';
else val = c - 'A' + 10;
// Chuyển đổi 4-bit
int b3 = (val >> 3) & 1;
int b2 = (val >> 2) & 1;
int b1 = (val >> 1) & 1;
int b0 = val & 1;
// In ra và xử lý số 0 đầu tiên
if (b3) { printf("1"); started = 1; }
else if (started || (i == len - 1 && !started)) printf("0");
if (b2) { printf("1"); started = 1; }
else if (started) printf("0");
if (b1) { printf("1"); started = 1; }
else if (started) printf("0");
if (b0) { printf("1"); started = 1; }
else if (started) printf("0");
}
printf("\n");
}
return 0;
}
- Time Complexity: O(T * L)
- Space Complexity: O(1)
Đây là cách tiếp cận trực tiếp và an toàn nhất. Thay vì cộng dồn thành số lớn, ta duyệt từng ký tự thập lục phân, dùng phép dịch bit hoặc mảng tra cứu để lấy 4 bit nhị phân tương ứng. Vấn đề chính là loại bỏ các số 0 ở đầu (leading zeros). Ta dùng biến cờ started để theo dõi đã in ra ký tự '1' lần đầu chưa. Nếu chưa in '1', ta chỉ in '0' khi ký tự đó là ký tự cuối cùng (trường hợp số input là '0').
Cách Dùng mảng tra cứu (Lookup Table)
#include <stdio.h>
#include <string.h>
const char* map[] = {
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
char hex[20];
scanf("%s", hex);
int len = strlen(hex);
int started = 0;
for (int i = 0; i < len; i++) {
char c = hex[i];
int idx = (c >= '0' && c <= '9') ? (c - '0') : (c - 'A' + 10);
const char* bits = map[idx];
// In 4 bit, bỏ qua leading zeros
for (int j = 0; j < 4; j++) {
if (bits[j] == '1') {
started = 1;
printf("1");
} else if (started) {
printf("0");
}
}
}
// Trường hợp đặc biệt: input là "0" -> không in gì (theo sample)
if (!started) printf("0");
printf("\n");
}
return 0;
}
- Time Complexity: O(T * L)
- Space Complexity: O(1)
Tương tự cách 2, nhưng thay vì tính toán bit mỗi lần, ta dùng mảng 16 phần tử chứa chuỗi nhị phân 4-bit. Cách này giúp code ngắn gọn hơn một chút và dễ đọc. Logic xử lý leading zeros vẫn giữ nguyên.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(L) | O(1) | Chuyển sang số nguyên rồi chia đôi (Không khả thi) |
| 2 | O(T * L) | O(1) | Map từng ký tự sang chuỗi nhị phân 4-bit |
| 3 | O(T * L) | O(1) | Dùng mảng tra cứu (Lookup Table) |
Bài học kinh nghiệm
- Mỗi ký tự thập lục phân tương ứng với chính xác 4 bit nhị phân.
- Do input có thể rất lớn (dù $10^{18}$ vẫn fit trong
long longnhưng $16^{16}$ thì không), cách an toàn nhất là xử lý chuỗi trực tiếp thay vì chuyển sang số. - Cần xử lý trường hợp số 0 ở đầu (leading zeros): chỉ in các bit '0' khi đã in ít nhất một bit '1', hoặc nếu toàn bộ input là '0' thì in một chữ số '0'.
Lỗi thường gặp
- Dùng
long longđể lưu giá trị số thập lục phân khi input có 16 ký tự 'F': $16^{16} - 1$ lớn hơn giá trị tối đa củaunsigned long long($2^{64}-1$), dẫn đến tràn số. - In ra các số 0 ở đầu (ví dụ: in "00001010" thay vì "1010").
- Quên in số 0 duy nhất khi input là "0".
Bình luận