OJ 1574 題解：找到最接近輸入值的 2 的冪次數

OJ 1574 題解：找到最接近輸入值的 2 的冪次數

給定一個長整數 a，找到與之最接近的 2 的冪次數（即 2^k 形式的數）。若有兩個同樣接近，輸出較大者。

算法思路

1. 找到不超過 a 的最大 2 的冪次 d = 2^k ≤ a。
2. 下一個冪次為 b = 2d = 2^{k+1}。
3. 比較 a - d 和 b - a，輸出差值較小者；相等時輸出較大的 b。

代碼實現

#include <stdio.h>

int main() {
    long a;
    scanf("%ld", &a);

    // 找到最大的 2^k <= a
    long d = 1;
    while (d * 2 <= a) d <<= 1;  // d *= 2

    long b = d << 1;  // 下一個冪次

    // 比較距離
    if (a - d < b - a)
        printf("%ld\n", d);
    else
        printf("%ld\n", b);

    return 0;
}

關鍵點解析

• 使用位運算 d <<= 1 高效計算 2 的冪次。
• 邊界情況：若 a 本身就是 2 的冪次，則 d = a，b = 2a，差值比較會正確選擇 d。
• 原文代碼用除法循環求 k 再用乘法還原，較繞彎；位運算更直觀高效。

複雜度

時間 O(log a)，空間 O(1)。