Số lớn hơn tiếp theo cùng số bit 1 (set bits) C++

Cho số n, tìm số nhỏ nhất > n có cùng số bit 1 trong biểu diễn nhị phân.

Ví dụ

n=124 (1111100₂, 5 bit 1) → 143 (10001111₂, 5 bit 1)

Thuật toán đơn giản (O(N))

• Đếm số bit 1 của n.
• Duyệt từ n+1 trở đi, tìm số đầu tiên có cùng số bit 1.

Thuật toán tối ưu O(1) - Bit Twiddling

int nextSameSetBits(int n) {
    int c = n;
    int c0 = 0, c1 = 0;
    while (((c & 1) == 0) && (c != 0)) { c0++; c >>= 1; }
    while ((c & 1) == 1) { c1++; c >>= 1; }
    if (c0 + c1 == 31 || c0 + c1 == 0) return -1; // overflow
    int p = c0 + c1;
    n |= (1 << p);        // set bit p
    n &= ~((1 << p) - 1); // clear bits below p
    n |= (1 << (c1 - 1)) - 1; // insert (c1-1) ones at right
    return n;
}

Triển khai đơn giản

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

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

int nextSameSetBitsSimple(int n) {
    int target = countSetBits(n);
    for (int i = n + 1; ; i++)
        if (countSetBits(i) == target) return i;
}

int main() {
    cout << nextSameSetBitsSimple(124) << endl; // 143
    return 0;
}

Kết quả

143