[TOC]

Các bài toán về hệ cơ số khá là phổ biến trong lập trình thi đấu, và bài viết này sẽ giới thiệu về khái niệm cũng như cách chuyển đổi giữa các hệ cơ số với nhau.

## Khái niệm
Trong các hệ đếm toán học, cơ số là số các chữ số của hệ đếm, bao gồm cả số 0 được dùng để biểu diễn số trong hệ đếm. Ví dụ, với hệ thập phân (hệ đếm sử dụng phổ biến nhất hiện này) cơ số là 10, vì hệ đếm này dùng mười chữ số từ 0 đến 9. ([wikipedia](https://vi.wikipedia.org/wiki/C%C6%A1_s%E1%BB%91))

Các hệ cơ số phổ biến thường gặp là hệ nhị phân (binary - hệ cơ số 2, gồm 2 chữ số duy nhất là 0 và 1, đây là hệ đếm phổ biến hay gặp nhất trong lập trình và có liên quan chặt chẽ đến bit), hệ bát phân (octal - hệ cơ số 8, gồm 8 chữ số từ 0 đến 7), hệ thập phân (decimal - hệ cơ số 10, gồm 10 chữ số từ 0 đến 9, đây là hệ số chúng ta dùng hằng ngày) và hệ thập lục phân (hexadecimal - hệ cơ số 16, gồm 10 chữ số từ 0 đến 9 và thêm 6 chữ cái từ A đến F).

Quy ước một số x đang biểu diễn ở hệ cơ số y sẽ được viết dưới dạng x~y~ (ví dụ 1001101 ở hệ cơ số 2 là 1001101~2~), tuy nhiên hệ thập phân thường có thể bỏ qua vì là hệ phổ biến thường dùng.

## Cách chuyển đổi
Xét số 825934 trong hệ thập phân. Ta có thể biểu diễn số đó dưới dạng:
8x100000 + 2x10000 + 5x1000 + 9x100 + 3x10 + 4x1
= 8x10^5^ + 2x10^4^ + 5x10^3^ + 9x10^2^ + 3x10^1^ + 4x10^0^
Xét từ phải sang trái, vì hệ thập phân có 10 chữ số nên mỗi chữ số sẽ được nhân với 10 lũy thừa vị trí của nó (vị trí bắt đầu từ 0 từ phải sang trái)
Hay nói cách khác, abcde~10~ = ex10^0^ + dx10^1^ + cx10^2^ + bx10^3^ + ax10^4^.

Tương tự với các hệ cơ số khác, lấy ví dụ như hệ nhị phân, vì chỉ có 2 chữ số có thể là 0 và 1 nên thay vì nhân cho lũy thừa của 10 ta sẽ nhân cho lũy thừa của 2
abcde~2~ = ex2^0^ + dx2^1^ + cx2^2^ + bx2^3^ + ax2^4^ để được số đó ở hệ thập phân.

Ngược lại, đối với hệ thập phân, (abcde)~10~ khi mod 10 (% 10) sẽ cho e, sau đó chia 10 được abcd, tiếp tục mod 10 được d rồi lại chia 10 cho tới khi bằng 0 thì dừng lại để được các chữ số a b c d e, thì đối với các hệ khác, lấy ví dụ như nhị phân, ta cũng có thể mod 2 và chia 2 để lấy các chữ số trong hệ nhị phân.

Thường các hệ cơ số không phải hệ thập phân sẽ dùng string chứ không dùng int vì đối với các hệ nhỏ hơn thập phân, độ dài số có thể sẽ rất dài và không thể dùng int (kể cả long long). Đối với các hệ lớn hơn thập phân, trong số sẽ bắt đầu xuất hiện chữ cái nên không thể dùng kiểu số.

#### Hệ nhị phân - Hệ thập phân
- Để chuyển từ hệ nhị phân sang thập phân, áp dụng công thức trên, đầu tiên ta tạo một biến để lưu lũy thừa 2 hiện tại, sau đó duyệt từ phải sang trái với string nhị phân và cộng chữ số tại vị trí đó nhân cho lũy thừa 2 hiện tại:

    #include <bits/stdc++.h>
    using namespace std;

    int bin_to_dec(string bin) {
        int dec = 0, po2 = 1; // power of 2, giá trị đầu tiên là 2^0 = 1
        for(int i = bin.size() - 1; i >= 0; i--) { // duyệt ngược về (từ phải sang trái)
            int tmp = bin[i] - '0'; // đổi từ char qua int
            dec += tmp * po2;
            po2 *= 2;
        }
        return dec;
    }

    int main() {

        cout << bin_to_dec("1001101"); // 77

        return 0;
    }

- Chuyển từ hệ thập phân sang nhị phân ta cũng áp dụng với cách làm ở trên:

    #include <bits/stdc++.h>
    using namespace std;

    string dec_to_bin(int dec) {
        if(dec == 0)
            return "0"; // vì while bên dưới chỉ chạy khi dec vẫn còn > 0 và sẽ trả về một string rỗng nên phải check trường hợp dec = 0
        string bin = "";
        while(dec > 0) {
            char tmp = (char)(dec % 2 + '0'); // đổi từ int qua char
            bin = tmp + bin; // thêm chữ số vào đầu
            dec /= 2;
        }
        return bin;
    }

    int main() {

        cout << dec_to_bin(77); // 1001101

        return 0;
    }

#### Hệ bát phân - Hệ thập phân
Tương tự như hệ nhị phân, hệ bát phân thay vì làm các phép toán với 2, ta chỉ cần đổi sang 8

- bát phân sang thập phân:

    #include <bits/stdc++.h>
    using namespace std;

    int oct_to_dec(string oct) {
        int dec = 0, po8 = 1;
        for(int i = oct.size() - 1; i >= 0; i--) {
            int tmp = oct[i] - '0';
            dec += tmp * po8;
            po8 *= 8;
        }
        return dec;
    }

    int main() {

        cout << oct_to_dec("247336"); // 85726

        return 0;
    }

- thập phân sang bát phân

    #include <bits/stdc++.h>
    using namespace std;

    string dec_to_oct(int dec) {
        if(dec == 0)
            return "0";
        string oct = "";
        while(dec > 0) {
            char tmp = (char)(dec % 8 + '0');
            oct = tmp + oct;
            dec /= 8;
        }
        return oct;
    }

    int main() {

        cout << dec_to_oct(67490); // 203642

        return 0;
    }

#### Hệ thập lục phân - Hệ thập phân
Trong hệ thập lục phân vì ngoài 9 chữ số còn có các chữ cái từ A đến F (A = 10, B = 11, C = 12, D = 13, E = 14, F = 15) nên phải xét thêm trường hợp là chữ cái hay số

- thập lục phân sang thập phân

    #include <bits/stdc++.h>
    using namespace std;

    int hex_to_dec(string hex) {
        int dec = 0, po16 = 1;
        for(int i = hex.size() - 1; i >= 0; i--) {
            int tmp;
            if(hex[i] >= '0' && hex[i] <= '9')
                tmp = hex[i] - '0';
            else
                tmp = hex[i] - 'A' + 10;
            dec += tmp * po16;
            po16 *= 16;
        }
        return dec;
    }

    int main() {

        cout << hex_to_dec("A8300FD"); // 176357629

        return 0;
    }

- thập phân sang thập lục phân

    #include <bits/stdc++.h>
    using namespace std;

    string dec_to_hex(int dec) {
        if(dec == 0)
            return "0";
        string hex = "";
        while(dec > 0) {
            char tmp;
            if(dec % 16 < 10)
                tmp = (char)(dec % 16 + '0');
            else
                tmp = (char)(dec % 16 - 10 + 'A');
            hex = tmp + hex;
            dec /= 16;
        }
        return hex;
    }

    int main() {

        cout << dec_to_hex(48828910); // 2E911EE

        return 0;
    }

Để chuyển từ một hệ x sang hệ y, ta có thể chuyển hệ x qua hệ thập phân trung gian sau đó chuyển sang hệ y