Đếm số chỉ có 1 bit được đặt trong phạm vi [0, n] trong C ++

Chúng tôi được cung cấp một số và nhiệm vụ là tính số lượng các số từ phạm vi 0 cho đến khi số đã cho, giả sử số có đúng một bit được đặt

Các bit tập hợp trong một số nhị phân được biểu diễn bằng 1. Bất cứ khi nào chúng ta tính toán số nhị phân của một giá trị số nguyên thì nó được tạo thành dưới dạng kết hợp của 0 và 1. Vì vậy, chữ số 1 được gọi là bit set trong các điều kiện của máy tính.

Đầu vào - int num =15

Đầu ra - Đếm số chỉ có 1 bit đặt trong phạm vi [0, 15] là - 4

Giải thích - Số đã cho là 15 nên phạm vi là 0-15. Bây giờ hãy tính 4 chữ số

số nhị phân cho -

0 -> 0000 =0 bit set, 1 -> 0001 =1 set bit, 2 -> 0010 =1 set bit, 3 -> 0011 =2 set bit, 4 -> 0100 =1 set bit, 5 -> 0101 =2 set bit, 6 -> 0110 =2 set bit, 7 -> 0111 =3 set bit, 8 -> 1000 =1 set bit, 1 -> 1001 =2 set bit, 10 -> 1010 =2 set bit, 11 -> 1011 =3 bit set, 12 -> 1100 =2 set bit, 13 -> 1101 =3 set bit, 14 -> 1110 =3 set bit, 15 -> 1111 =4 set bit. Bây giờ, chúng ta sẽ chọn các số có đúng một bit được đặt và đó là 1, 2, 4 và 8.

Đầu vào - int num =4

Đầu ra - Đếm số chỉ có 1 bit đặt trong phạm vi [0, 15] là - 3

Giải thích - Số đã cho là 4 nên dãy số là 0-4. Bây giờ hãy tính toán nhị phân 4 chữ số

số cho -

0 -> 0000 =0 bit set, 1 -> 0001 =1 set bit, 2 -> 0010 =1 set bit, 3 -> 0011 =2 set bit, 4 -> 0100 =1 set bit. Bây giờ, chúng ta sẽ chọn các số có đúng một bit được đặt và đó là 1, 2 và 4.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Có thể có nhiều cách tiếp cận để giải quyết vấn đề đã cho, tức là cách tiếp cận ngây thơ và cách tiếp cận hiệu quả. Vì vậy, trước tiên chúng ta hãy xem xét cách tiếp cận ngây thơ .

Nhập số và chuyển nó cho hàm để xử lý thêm.
Lấy một số lượng biến tạm thời để lưu trữ số lượng các số trong phạm vi với bit đặt chính xác là 1
Bắt đầu vòng lặp FOR từ i đến 1 cho đến số
Bên trong vòng lặp, hãy đặt một biến tạm thời với ‘__builtin_popcount (i)’, hàm trả về số lượng các bit đã đặt.
Kiểm tra IF temp =1 rồi tăng số lượng
Số lần trả lại
In kết quả

Cách tiếp cận hiệu quả

Nhập số và chuyển nó cho hàm để xử lý thêm.
Lấy một số lượng biến tạm thời để lưu trữ số lượng các số trong phạm vi với bit đặt chính xác là 1
Bắt đầu vòng lặp Trong khi từ nhiệt độ đến nhiệt độ <=number
Bên trong vòng lặp, tăng số đếm lên 1 và đặt nhiệt độ là tạm thời * 2
Số lần trả lại
In kết quả

Ví dụ (cách tiếp cận ngây thơ)

#include <iostream>
using namespace std;
//function to Count of numbers having only 1 set bit in the range [0, n]
int set_bits(int number){
   int count = 0;
   for (int i = 1; i <= number; i++){
      int temp = __builtin_popcount(i);
      if (temp == 1){
         count++;
      }
   }
   return count;
}
int main(){
   int number = 15;
   cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of numbers having only 1 set bit in the range [0, 15] are: 4

Ví dụ (Cách tiếp cận hiệu quả)

#include <iostream>
using namespace std;
//function to Count of numbers having only 1 set bit in the range [0, n]
int set_bits(int number){
   int count = 0;
   int temp = 1;
   while(temp <= number){
      count++;
      temp = temp *2;
   }
   return count;
}
int main(){
   int number = 15;
   cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of numbers having only 1 set bit in the range [0, 15] are: 4