Editorial for cvb2h: Đổi hệ nhị phân sang hệ cơ số 16

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ệ nhị phân (cơ số 2) sang hệ thập lục phân (cơ số 16). Đầu vào gồm nhiều test case, mỗi test case là một xâu ký tự biểu diễn số nhị phân. Độ dài xâu nhị phân tối đa là 63, đủ để lưu trong kiểu số nguyên 64-bit (long long).

Các cách tiếp cận

Cách Sử dụng hàm chuyển đổi có sẵn (Library Function)

#include <stdio.h>
#include <stdlib.h>

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        char binary[1001];
        scanf("%s", binary);
        long long decimal = strtoll(binary, NULL, 2);
        printf("%llX\n", decimal);
    }
}

• Time Complexity: O(N) cho mỗi test case, với N là độ dài xâu nhị phân.
• Space Complexity: O(1) (không tính bộ nhớ cho xâu đầu vào).

Cách này tận dụng thư viện chuẩn của C. Hàm strtoll(binary, NULL, 2) chuyển đổi xâu kí tự binary (với cơ số 2) thành số nguyên dạng long long. Sau đó, ta sử dụng format specifier %llX trong hàm printf để in ra số đó ở dạng thập lục phân (uppercase) một cách tự động. Đây là cách ngắn gọn và hiệu quả nhất.

Cách Chuyển đổi từng bước (Tính toán thủ công)

#include <stdio.h>
#include <string.h>

int main() {
    int a;
    scanf("%d", &a);
    while (a--) {
        char s[64];
        scanf("%s", s);
        long long x = 0;
        int len = strlen(s);
        // Chuyển nhị phân sang thập phân
        for (int i = 0; i < len; i++) {
            x = x * 2 + (s[i] - '0');
        }

        // Chuyển thập phân sang thập lục phân
        if (x == 0) {
            printf("0\n");
            continue;
        }
        char hex[20];
        int idx = 0;
        while (x > 0) {
            int remainder = x % 16;
            if (remainder < 10) hex[idx++] = remainder + '0';
            else hex[idx++] = remainder - 10 + 'A';
            x /= 16;
        }
        // In kết quả ngược (do lưu từ số thấp lên cao)
        for (int i = idx - 1; i >= 0; i--) {
            printf("%c", hex[i]);
        }
        printf("\n");
    }
}

• Time Complexity: O(N) cho mỗi test case.
• Space Complexity: O(1).

Phương pháp này thực hiện thủ công từng bước:

1. Xét từng ký tự nhị phân, tính giá trị số học (kiểu long long) bằng cách nhân 2 và cộng bit.
2. Chia đôi số vừa tính cho 16, lấy số dư để tạo thành ký tự thập lục phân (0-9 hoặc A-F).
3. Lưu các ký tự vào mảng (thường là ngược chiều) và in ra. Cần chú ý xử lý trường hợp số bằng 0 nếu dùng vòng lặp while (vì while (x>0) sẽ không chạy).

Cách Quy đổi trực tiếp theo nhóm 4-bit

#include <stdio.h>
#include <string.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char s[65];
        scanf("%s", s);
        int len = strlen(s);

        // In các ký tự đầu tiên không thuộc nhóm 4 (nếu có)
        int first_group_len = len % 4;
        if (first_group_len == 0) first_group_len = 4;

        int val = 0;
        int i = 0;
        // Xử lý phần thừa ra
        for (; i < first_group_len; i++) {
            val = val * 2 + (s[i] - '0');
        }
        printf("%X", val);

        // Xử lý các nhóm 4-bit còn lại
        for (; i < len; i += 4) {
            val = 0;
            for (int j = 0; j < 4; j++) {
                val = val * 2 + (s[i+j] - '0');
            }
            printf("%X", val);
        }
        printf("\n");
    }
}

• Time Complexity: O(N) cho mỗi test case.
• Space Complexity: O(1) (không cần mảng phụ lưu kết quả).

Đây là cách quy đổi trực tiếp dựa trên đặc tính cơ số: 16 = 2^4. Ta có thể nhóm các bit nhị phân thành nhóm 4 (từ phải sang trái) và chuyển mỗi nhóm thành 1 ký tự thập lục phân.

• Nếu độ dài xâu không chia hết cho 4, phần thừa ở đầu sẽ được xử lý riêng.
• Cách này không cần lưu trữ kết quả vào mảng phụ mà có thể in ra ngay lập tức, rất hiệu quả về bộ nhớ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Kiểu dữ liệu long long (64-bit) ở C/C++ có thể lưu số thập phân tương ứng với xâu nhị phân độ dài tối đa 63 (vì 2^63 ~ 9e18, nằm trong giới hạn ~9e18 của long long).
• Có thể chuyển đổi trực tiếp từ nhị phân sang thập lục phân bằng cách nhóm 4 bit (vì 16 = 2^4), bỏ qua bước trung gian tính ra số thập phân.
• Sử dụng format specifier printf("%llX", number) là cách nhanh nhất để in số nguyên long long ở dạng hexadecimal trong C.

Lỗi thường gặp

• Quên xử lý trường hợp input là "0" khi viết vòng lặp chuyển đổi thủ công (ví dụ: vòng lặp while(x > 0) sẽ không chạy nếu x ban đầu bằng 0, dẫn đến không in ra gì).
• Tràn số (Overflow) nếu dùng int thay vì long long để lưu giá trị số học.
• Sử dụng hàm pow() trong vòng lặp để tính lũy thừa nhị phân (như Solution 2) làm chậm chương trình và có thể gặp lỗi làm tròn số thực.