C 語言區間二進制位數和最大值：暴力解法與優化思路

題目：給定區間 [L, R)，找出二進制表示中 1 的個數（人口計數）最多的整數；若有多個，輸出最小者。

暴力解法

int popcount(int x) {
    int c = 0;
    while (x) { c += x & 1; x >>= 1; }
    return c;
}

int main() {
    int L, R;
    while (scanf("%d %d", &L, &R) == 2) {
        int best = L, maxBits = popcount(L);
        for (int i = L + 1; i < R; ++i) {
            int bits = popcount(i);
            if (bits > maxBits) { maxBits = bits; best = i; }
        }
        printf("%d\n", best);
    }
    return 0;
}

優化觀察

• 區間上限為 int 範圍，暴力最多遍歷 2^31 次，不可行。
• 最多 1 的數字通常是形如 2^k - 1（全 1）或接近該形式。
• 可從高位向低位貪婪構造：在 R-1 基礎上，嘗試將某 0 位改為 1、後續位全設 1，檢查是否仍 ≥ L，取最大人口計數者。

本文提供暴力版供小範圍驗證，大範圍請參考貪婪構造或 DP 位運算解法。