a034. 二進位制轉換

Easy Last Update: 2025/05/16

基本運算進制轉換

給一個十進制數字 n
將其轉成二進制

※ 注意，正常情況需要對 0 做特判 (以下寫法會把 0 當前綴 0 去掉，也就是不會輸出)
(但是測資沒有 0，既然測資沒有，那麼我也得偷懶一下)

解法一、取餘數

n % 2 能夠取得 n 的最低位二進位數字 (0 或 1)
對 n 不斷除以 2，直到 n 變成 0

✅ 完整代碼

評分結果(參考) ： AC (2ms, 332KB)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while(cin >> n){
        string s;
        while(n != 0){
            s = (char)(n%2 + '0') + s;
            n /= 2;    
        }
        cout << s << "\n";
    }
    
    return 0;
}

優化

🔹 運算優化

n % 2 優化 (n & 1)
n / 2 優化 (n >>= 1)

🔹 字串加法優化

s = c + s; 每次需要複製一份 s，再用 c 加上他
複製的過程是 $O(s.length)$
如果有 n 個字元 c 那麼時間複雜度是 $O(N^{2})$

s += c; 每次只要在 s 後面加上 c
這個過程是 $O(1)$
全部加完後反轉字串
如果有 n 個字元 c 那麼時間複雜度是 $O(N)$

(雖然測資小優化不是很必要)

✅ 優化後代碼

評分結果(參考) ： AC (2ms, 324KB)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while(cin >> n){
        string s;
        while(n != 0){
            s += (char)((n&1) + '0');
            n >>= 1;
        }
        reverse(s.begin(), s.end());
        cout << s << "\n";
    }
    
    return 0;
}

解法二、bitset

✅ 完整代碼

評分結果(參考) ： AC (2ms, 332KB)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while(cin >> n){
        bitset<31> b(n);

        bool ignore0 = true;
        for(int i=31; i>=0; i--){
            if(b[i] || i==0) ignore0 = false;
            if(!ignore0) cout << b[i];
        }
        cout << "\n";
    }
    
    return 0;
}