Chương trình tìm chuỗi 1 liên tiếp dài nhất trong dạng nhị phân của số trong C++

Cho một số nguyên n. Tìm độ dài chuỗi các bit 1 liên tiếp dài nhất trong biểu diễn nhị phân của n.

Ví dụ: n = 312 → nhị phân 100111000 → có 3 bit 1 liên tiếp → kết quả 3.

Thuật toán

• Khởi tạo ret = 0, len = 0.
• Duyệt 32 bit (int 32-bit): dịch phải n i lần, AND với 1 để lấy bit thứ i.
• Nếu bit = 1: tăng len, cập nhật ret = max(ret, len).
• Nếu bit = 0: reset len = 0.
• Trả về ret.

Ví dụ triển khai (C++)

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

class Solution {
public:
    int solve(int n) {
        int ret = 0, len = 0;
        for (int i = 0; i < 32; i++) {
            if ((n >> i) & 1) len++;
            else len = 0;
            ret = max(ret, len);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve(312);
    return 0;
}

Đầu vào

312

Đầu ra

3