เราได้รับตัวเลขและภารกิจคือการคำนวณการนับตัวเลขจากช่วง 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
