Số lớn nhất có dạng m bit 1 và m-1 bit 0 C++

Tìm số lớn nhất ≤ N có dạng nhị phân: m bit 1 liên tiếp theo sau m-1 bit 0 liên tiếp.

Ví dụ: m=3 → 11100₂ = 28; m=4 → 1111000₂ = 120.

Công thức: (2^m - 1) * 2^(m-1) = 2^(2m-1) - 2^(m-1)

Thuật toán

• Duyệt m = 2, 3, ... tính giá trị.
• Lấy giá trị lớn nhất ≤ N.

Triển khai C++

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

long long largestMOnesMminus1Zeros(long long N) {
    long long ans = 1; // m=1 -> 1
    for (int m = 2; ; m++) {
        long long val = ((1LL << m) - 1) << (m - 1);
        if (val > N) break;
        ans = val;
    }
    return ans;
}

int main() {
    cout << largestMOnesMminus1Zeros(654) << endl; // 496 (m=5: 111110000)
    return 0;
}

Kết quả

496