九度 OJ 1473 題解：無符號整數轉二進制字串 (去除前導零)

題目描述

給定 T 個無符號整數 (0 ≤ n ≤ 10⁸)，輸出其二進制表示，**去除前導零**。T ≤ 1000。

範例

輸入：
5
23
535
2624
56275
989835

輸出：
10111
1000010111
101001000000
1101101111010011
11110001101010001011

演算法分析

1. 特判 n == 0 直接輸出 0
2. 反覆 n % 2 取餘 (得最低位)，n /= 2 右移
3. 將餘數存入列表/陣列 (逆序產生)
4. 反向輸出即為正確二進制字串
5. 時間複雜度 O(log n)，空間 O(log n)

Java 完整解法

import java.util.ArrayList;
import java.util.Scanner;

public class Q1473 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        int[] inputs = new int[T];
        for (int i = 0; i < T; i++) {
            inputs[i] = scanner.nextInt();
        }
        
        for (int n : inputs) {
            if (n == 0) {
                System.out.println("0");
                continue;
            }
            
            ArrayList bits = new ArrayList<>();
            while (n != 0) {
                bits.add(n % 2);
                n /= 2;
            }
            
            // 反向輸出
            for (int i = bits.size() - 1; i >= 0; i--) {
                System.out.print(bits.get(i));
            }
            System.out.println();
        }
        scanner.close();
    }
}

進階優化版 (位運算 + StringBuilder)

public class Q1473Optimized {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuilder output = new StringBuilder();
        
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            output.append(toBinaryString(n)).append('\n');
        }
        System.out.print(output);
        sc.close();
    }
    
    // 手工實現 (教學用)，生產請用 Integer.toBinaryString(n)
    private static String toBinaryString(int n) {
        if (n == 0) return "0";
        char[] buf = new char[32]; // int 最大 32 位
        int idx = buf.length;
        while (n != 0) {
            buf[--idx] = (char) ('0' + (n & 1)); // 位運算取最低位
            n >>>= 1; // 無符號右移
        }
        return new String(buf, idx, buf.length - idx);
    }
}

關鍵技術點

Java 庫函數一行解 (實務推薦)

System.out.println(Integer.toBinaryString(n));

• 自動處理 0、負數 (補碼 32 位)、前導零
• JDK 內部優化極佳 (查表法 + 位運算)
• 面試/考試若要求手寫，使用上述手工實現

擴展：長整數 / BigInteger