Số lớn hơn N có nhiều hơn 1 bit 1 C++

Cho n, tìm số nhỏ nhất > n có số bit 1 = popcount(n) + 1.

Ví dụ

n=124 (1111100₂, 5 bit 1) → 125 (1111101₂, 6 bit 1)

Thuật toán

• Đếm bit 1 của n.
• Duyệt từ n+1 tìm số có bit 1 = target + 1.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

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

int nextMoreSetBits(int n) {
    int target = popcount(n) + 1;
    for (int i = n + 1; ; i++)
        if (popcount(i) == target) return i;
}

int main() {
    cout << nextMoreSetBits(124) << endl; // 125
    return 0;
}

Kết quả

125