ACM 經典題：下一個相同 1 個數的二進制數

下一個相同 1 個數的二進制數

給定正整數 n，找出大於 n 的最小整數，使其二進制中 1 的個數相同。例如 78 (1001110, 四個 1) → 83 (1010011, 四個 1)。

暴力解法（教學用）

從 n+1 開始逐個檢查，統計 1 的個數，相等即輸出。雖然簡單但對大數效率低。

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

int main() {
    int n;
    while(cin >> n, n) {
        int target = countOnes(n);
        for(int i = n+1; ; i++)
            if(countOnes(i) == target) { cout << i << '\n'; break; }
    }
}

位運算優化解法（O(1)）

經典「下一個排列」位運算技巧（Next Higher Number with Same Number of 1 Bits）：

1. `c = n & -n`：提取最低位的 1。
2. `r = n + c`：將該 1 進位，低位歸零。
3. `n = (((r ^ n) >> 2) / c) | r`：將進位後多出的 1 移到最低位。

int nextSameOnes(int n) {
    int c = n & -n;
    int r = n + c;
    return (((r ^ n) >> 2) / c) | r;
}

原理解析

• 找到最右邊的「01」模式（即最低位的 1 及其左側的 0）。
• 將其變為「10」，並將右側所有 1 移到最低位。
• 例如 78 = 1001110 → 最右「01」在倒數第 3,4 位 → 變為 1010011 = 83。

完整程序

#include <cstdio>
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        int c = n & -n;
        int r = n + c;
        int ans = (((r ^ n) >> 2) / c) | r;
        printf("%d\n", ans);
    }
    return 0;
}

測試樣例

輸入: 1 2 3 4 78 0
輸出: 2 4 5 8 83

總結

位運算技巧將 O(n) 暴力優化為 O(1)，是位運算經典應用。理解「最右 01 翻轉 + 右側 1 右移」的邏輯是關鍵。