UVA 10976 / POJ 1028 - Binary Numbers 解題詳解與 C 語言實現

題目概述

本題要求對輸入的整數進行二進制轉換，並輸出所有值為 1 的位元位置（從最低位開始計數，索引從 0 起算）。多組測試資料之間需換行分隔。

核心演算法邏輯

程式採用位元運算逐位檢查：

• 使用 num % 2 == 1 判斷最低位是否為 1
• 透過 num /= 2 右移除去已檢查的位元
• count 變數記錄當前位元索引
• flag 控制輸出格式，避免前導空格

完整 C 語言程式碼

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

int main() {
    int n, num, count, flag;
    scanf("%d", &n);
    while (n--) {
        count = flag = 0;
        scanf("%d", &num);
        while (num) {
            if (num % 2 == 1) {
                if (flag) printf(" ");
                printf("%d", count);
                flag = 1;
            }
            count++;
            num /= 2;
        }
        if (n > 0) printf("\n");
    }
    return 0;
}

關鍵點解析

輸入處理： 先讀取測試案例數 n，迴圈處理每組資料。

位元遍歷： while(num) 迴圈在數值變為 0 時終止，自動忽略高位前導零。

格式控制： flag 確保第一個位置索引前無空格，後續索引前加單一空格；測試案例間以換行分隔。

複雜度分析

• 時間複雜度：O(log₂ num) 每測試案例
• 空間複雜度：O(1)

常見陷阱提醒

• 輸入值為 0 時，while(num) 不執行，輸出空行（符合題意：無 1 位元）
• 最後一組測試資料後不應有多餘換行，if(n>0) 判斷恰當處理此點