Đếm số có toàn bit 1 trong biểu diễn nhị phân trong C++

Cho một số nguyên dương N. Mục tiêu là đếm các số nhỏ hơn hoặc bằng N mà biểu diễn nhị phân của chúng chỉ chứa toàn bit 1. Ví dụ: 1 là 1, 3 là 11, 7 là 111, 15 là 1111, v.v.

Nếu quan sát các số này, tất cả đều có dạng 2^i - 1, với i bắt đầu từ 1. Để kiểm tra các số như vậy nhỏ hơn n, ta so sánh nếu 2^i - 1 <= n thì tăng biến đếm.

Hãy hiểu qua các ví dụ.

Đầu vào − N=15

Đầu ra − Số có toàn bit 1 trong nhị phân: 4

Giải thích − Các số là: 1, 3, 7, 15

Đầu vào − N=50

Đầu ra − Số có toàn bit 1 trong nhị phân: 5

Giải thích − Các số thỏa mãn điều kiện

Phương pháp sử dụng trong chương trình dưới đây

• Nhận số nguyên dương N.
• Hàm allOnes(int n) nhận n làm đầu vào và trả về số lượng số có toàn bit 1 trong biểu diễn nhị phân.
• Khởi tạo biến count = 0 cho các số như vậy.
• Duyệt từ i=1 đến i<=n bằng vòng lặp for.
• Với mỗi i, nếu pow(2,i)-1 nhỏ hơn hoặc bằng n thì tăng count.
• Trả về count làm kết quả sau khi kết thúc vòng lặp.

Ví dụ

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

int allOnes(int n) {
    int count = 0;
    for(int i=1; i<=n; i++) {
        if(n >= pow(2,i)-1) {
            count++;
            // cout << " " << pow(2,i)-1;
        }
    }
    return count;
}

int main() {
    int N=23;
    cout << endl << "Số có toàn bit 1 trong nhị phân: " << allOnes(N);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số có toàn bit 1 trong nhị phân: 4