Editorial for cvb2d: Đổi hệ nhị phân sang thập 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 được biểu diễn dưới dạng chuỗi ký tự trong hệ nhị phân (cơ số 2) sang dạng số nguyên trong hệ thập phân (cơ số 10). Số lượng bộ test T có thể lên tới 100,000, nhưng độ dài mỗi chuỗi nhị phân không vượt quá 63. Do đó, kết quả có thể nằm trong khoảng từ 0 đến 2^63 - 1, nên cần sử dụng kiểu dữ liệu lưu trữ số nguyên lớn (ví dụ: long long trong C/C++).

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

Cách Sử dụng hàm lũy thừa (pow)

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

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        char s[64];
        scanf("%s", s);
        int len = strlen(s);
        long long x = 0;
        // Duyệt từ bit có trọng số thấp nhất (cuối chuỗi) tới cao nhất
        for (int i = len - 1; i >= 0; i--) {
            // Tính trọng số 2^(len - 1 - i) và cộng dồn
            // (Trong code mẫu dùng biến đếm cnt từ 0)
            x += (s[i] - '0') * (1LL << (len - 1 - i));
        }
        printf("%lld\n", x);
    }
    return 0;
}

• Time Complexity: O(N) với N là độ dài chuỗi
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng trực tiếp công thức giá trị của số trong cơ số 2. Nó duyệt chuỗi từ phải sang trái (hoặc dùng biến đếm trọng số) và tính giá trị của từng bit bằng cách nhân với 2 mũ (2^0, 2^1, ...) rồi cộng dồn lại.

Trong giải pháp tham khảo:

• Solution 1 sử dụng hàm pow(2, cnt) từ thư viện math.h. Hàm này trả về kiểu double, sau đó ép kiểu sang long long. Tuy nhiên, pow là hàm tính toán số thực, có thể chậm hơn phép toán bit và tiềm ẩn sai số làm tròn nếu số quá lớn (dù trong giới hạn 63 bit thì double vẫn đủ精度, nhưng không tối ưu).

Cách Phép nhân và cộng liên tục (Horner's Method / Duyệt từ trái sang phải)

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

long long chuyen(char s[]) {
    long long ket_qua = 0;
    int do_dai = strlen(s);
    for (int i = 0; i < do_dai; i++) {
        int bit = s[i] - '0';
        // Dịch trái (nhân 2) và cộng bit mới
        ket_qua = ket_qua * 2 + bit;
    }
    return ket_qua;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        char s[65];
        scanf("%s", s);
        printf("%lld\n", chuyen(s));
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là cách hiệu quả hơn để chuyển đổi cơ số. Thay vì tính lũy thừa cho mỗi bit, ta duyệt chuỗi từ trái sang phải (từ bit có trọng số cao nhất).

Giả sử ta đang có kết quả của các bit trước đó là val. Khi gặp bit mới b, giá trị mới sẽ là val * 2 + b. Ví dụ: "101"

1. val = 0*2 + 1 = 1
2. val = 1*2 + 0 = 2
3. val = 2*2 + 1 = 5

Phương pháp này chỉ cần phép nhân và cộng đơn giản, rất nhanh và tránh được các hàm thư viện.

Cách Sử dụng bit shift (Dịch bit)

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

typedef long long ll;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char s[101];
        scanf("%s", s);
        ll sum = 0;
        int len = strlen(s);
        for (int i = 0; i < len; i++) {
            // Dịch trái 1 bit tương đương nhân 2
            sum = (sum << 1) + (s[i] - '0');
        }
        printf("%lld\n", sum);
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là biến thể của phương pháp "Phép nhân và cộng", sử dụng thao tác bit-level. sum << 1 thực hiện phép nhân 2 bằng cách dịch bit sang trái. Về mặt hiệu năng, hai phép sum * 2 và sum << 1 thường biên dịch ra cùng một câu lệnh máy (nhân với 2), nhưng << thường được coi là biểu hiện rõ ràng hơn của thao tác bit.

Code tham khảo (Solution 3) cũng xử lý việc nhập xuất chuẩn xác hơn (dùng getchar, fgets để loại bỏ ký tự newline), nhưng logic chuyển đổi cơ bản vẫn là dùng bit shift.

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

Bài học kinh nghiệm

• Có thể chuyển đổi trực tiếp khi đọc chuỗi mà không cần tính lũy thừa cho từng bit.
• Phép nhân cơ số 2 tương đương với phép dịch bit trái 1 đơn vị.
• Kiểu dữ liệu long long là bắt buộc vì kết quả có thể lên tới ~9 * 10^18.

Lỗi thường gặp

• Sử dụng int thay cho long long dẫn đến tràn số khi chuỗi nhị phân dài trên 31 bit.
• Lỗi nhập xuất: Cần chú ý ký tự newline '\n' khi dùng scanf kết hợp với các hàm đọc chuỗi sau đó.
• Độ dài chuỗi đủ lớn để chứa null terminator: char s[64] cho chuỗi dài 63 ký tự.