Số lượng 0 tối đa giữa hai bit 1 liên tiếp trong biểu diễn nhị phân trong C++

Đề bài

Cho số n, tìm số lượng bit 0 liên tiếp nhiều nhất giữa hai bit 1 liền kề nhau trong biểu diễn nhị phân. Trả về -1 nếu có ít hơn 2 bit 1.

Ví dụ: n=35 (nhị phân 100011) → có 3 bit 0 giữa hai bit 1 giữa → kết quả 3.

Thuật toán (Dịch bit)

1. Nếu n=0 hoặc n là lũy thừa của 2 → trả về -1 (chỉ có 1 bit 1).
2. Tìm vị trí bit 1 đầu tiên từ phải (LSB) → prev.
3. Duyệt các bit tiếp theo, mỗi khi gặp bit 1 tại vị trí cur, cập nhật maxZeros = max(maxZeros, cur - prev - 1), gán prev = cur.

Ví dụ minh họa (C++)

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

int getMaxZeros(int n) {
    if (n == 0 || (n & (n - 1)) == 0) return -1; // 0 hoặc power of 2
    int setBit = 1;
    int prev = 0, i;
    // Tìm bit 1 đầu tiên
    for (i = 1; i < sizeof(int)*8; ++i) {
        ++prev;
        if ((n & setBit) == setBit) { setBit <<= 1; break; }
        setBit <<= 1;
    }
    int maxZeros = INT_MIN;
    int cur = prev;
    // Duyệt các bit tiếp theo
    for (int j = i + 1; j <= sizeof(int)*8; ++j) {
        ++cur;
        if ((n & setBit) == setBit) {
            if (maxZeros < cur - prev - 1) { maxZeros = cur - prev - 1; prev = cur; }
        }
        setBit <<= 1;
    }
    return maxZeros;
}

int main() {
    int n = 35;
    cout << "So 0 lon nhat giua hai 1 lien tiep = " << getMaxZeros(n) << endl;
    return 0;
}

Kết quả

So 0 lon nhat giua hai 1 lien tiep = 3