การนับจำนวนที่มีเพียง 1 ชุดบิตในช่วง [0, n] ใน C++

เราได้รับตัวเลขและภารกิจคือการคำนวณการนับตัวเลขจากช่วง 0 จนถึงจำนวนที่กำหนด สมมติว่า num มีหนึ่งชุดบิตที่แน่นอน

ชุดบิตในเลขฐานสองจะถูกแทนด้วย 1 เมื่อใดก็ตามที่เราคำนวณเลขฐานสองของค่าจำนวนเต็ม มันจะถูกสร้างขึ้นเป็นการรวมกันของ 0 และ 1 ดังนั้น ตัวเลข 1 จึงเรียกว่า set bit ในแง่ของคอมพิวเตอร์

ป้อนข้อมูล − int num =15

ผลผลิต − จำนวนตัวเลขที่มีเพียง 1 ชุดบิตในช่วง [0, 15] คือ − 4

คำอธิบาย − ตัวเลขที่ระบุคือ 15 ดังนั้นช่วงคือ 0-15 ตอนนี้คำนวณ 4 หลัก

เลขฐานสองสำหรับ −

0 -> 0000 =0 ชุดบิต 1 -> 0001 =1 ชุดบิต 2 -> 0010 =1 ชุดบิต 3 -> 0011 =2 ชุดบิต 4 -> 0100 =1 ชุดบิต 5 -> 0101 =2 ชุดบิต 6 -> 0110 =2 ชุดบิต 7 -> 0111 =3 ชุดบิต 8 -> 1000 =1 ชุดบิต 1 -> 1001 =2 ชุดบิต 10 -> 1010 =2 ชุดบิต 11 -> 1011 =3 ชุดบิต 12 -> 1100 =2 ชุดบิต 13 -> 1101 =3 ชุดบิต 14 -> 1110 =3 ชุดบิต 15 -> 1111 =4 ชุดบิต ตอนนี้เราจะเลือกตัวเลขที่มีบิตเซ็ตเดียว นั่นคือ 1, 2, 4 และ 8

ป้อนข้อมูล − int num =4

ผลผลิต − จำนวนตัวเลขที่มีเพียง 1 ชุดบิตในช่วง [0, 15] คือ − 3

คำอธิบาย − จำนวนที่กำหนดคือ 4 ดังนั้นช่วงคือ 0-4 ตอนนี้คำนวณเลขฐานสอง 4 หลัก

หมายเลขสำหรับ −

0 -> 0000 =0 ชุดบิต 1 -> 0001 =1 ชุดบิต 2 -> 0010 =1 ชุดบิต 3 -> 0011 =2 ชุดบิต 4 -> 0100 =1 ชุดบิต ตอนนี้เราจะเลือกตัวเลขที่มีบิตชุดเดียว นั่นคือ 1, 2 และ 4

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน .

• ป้อนหมายเลขแล้วส่งต่อไปยังฟังก์ชันเพื่อดำเนินการต่อไป

• ใช้การนับตัวแปรชั่วคราวเพื่อเก็บการนับจำนวนในช่วงโดยกำหนดให้บิตเป็น 1

• เริ่มวนซ้ำ FOR จาก i ถึง 1 จนถึงจำนวน

• ภายในลูป ให้ตั้งค่าตัวแปร temp ด้วย ' __builtin_popcount(i)' ซึ่งเป็นฟังก์ชันที่คืนค่าจำนวนบิตที่ตั้งไว้

• ตรวจสอบ IF temp =1 แล้วเพิ่มการนับ

• จำนวนคืน

• พิมพ์ผล

แนวทางที่มีประสิทธิภาพ

• ป้อนหมายเลขแล้วส่งต่อไปยังฟังก์ชันเพื่อดำเนินการต่อไป

• ใช้การนับตัวแปรชั่วคราวเพื่อเก็บการนับจำนวนในช่วงโดยกำหนดให้บิตเป็น 1

• เริ่มวนรอบในขณะที่จาก temp ถึง temp <=number

• ภายในลูป ให้เพิ่มจำนวนขึ้น 1 และตั้งค่า temp เป็น temp * 2

• จำนวนคืน

• พิมพ์ผล

ตัวอย่าง (แนวทางไร้เดียงสา)

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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

ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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