Tìm số có bit 1 chỉ trong khoảng [L, R] bằng C++

Cho khoảng [L, R] (chỉ số bit, 0-based), tìm số có tất cả bit từ L đến R = 1, các bit khác = 0. Ví dụ:

Input: L=1, R=5 → 62 (binary ...111110) Input: L=1, R=4 → 30 (binary ...11110)

Cách vét cạn O(R-L)

Cộng 2ⁱ cho i = L..R.

Ví dụ

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

int main() {
    int L = 1, R = 3, ans = 0;
    for(int i = L; i <= R; i++) ans += pow(2, i);
    cout << ans << "\n";
}

Kết quả

14

Cách hiệu quả O(1): Công thức bit

Số có bit 1 từ 0 đến R = (1 << (R+1)) - 1. Số có bit 1 từ 0 đến L-1 = (1 << L) - 1. Kết quả = hiệu hai số trên: ((1 << (R+1)) - 1) ^ ((1 << L) - 1) hoặc ((1 << (R+1)) - 1) - ((1 << L) - 1).

Ví dụ (sửa lỗi code gốc)

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

int main() {
    int L = 1, R = 3;
    int ans = ((1 << (R + 1)) - 1) ^ ((1 << L) - 1);
    cout << ans << "\n";
    return 0;
}

Kết quả

14

Kết luận

Tìm số có bit 1 chỉ trong khoảng [L,R] bằng công thức bit O(1). Code C++ mẫu.