เราได้รับตัวเลขและงานคือการคำนวณจำนวนตัวเลขจากช่วง 0 ถึงตัวเลขที่กำหนดสมมติว่า num ที่มีบิตเซ็ต (set bit) เพียง 1 ตัวเท่านั้น
บิตเซ็ตในตัวเลขไบนารีแทนด้วย 1 ทุกครั้งที่เราคำนวณตัวเลขไบนารีของค่าจำนวนเต็ม มันจะประกอบด้วย 0 และ 1 ดังนั้น ตัวเลข 1 จึงเรียกว่า set bit ในทางคอมพิวเตอร์
อินพุต − int num = 15
เอาต์พุต − นับจำนวนที่มีบิตเซ็ตเพียง 1 ตัวในช่วง [0, 15] คือ − 4
คำอธิบาย − ตัวเลขที่กำหนดคือ 15 ดังนั้นช่วงคือ 0-15 คำนวณตัวเลขไบนารี 4 หลักสำหรับ: 0 → 0000 = 0 set bit, 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, 9 → 1001 = 2 set bit, 10 → 1010 = 2 set bit, 11 → 1011 = 3 set bit, 12 → 1100 = 2 set bit, 13 → 1101 = 3 set bit, 14 → 1110 = 3 set bit, 15 → 1111 = 4 set bits ตอนนี้เราจะเลือกตัวเลขที่มีบิตเซ็ตเพียง 1 ตัว และได้คือ 1, 2, 4 และ 8
อินพุต − int num = 4
เอาต์พุต − นับจำนวนที่มีบิตเซ็ตเพียง 1 ตัวในช่วง [0, 15] คือ − 3
คำอธิบาย − ตัวเลขที่กำหนดคือ 4 ดังนั้นช่วงคือ 0-4 คำนวณไบนารี 4 หลักสำหรับ: 0 → 0000 = 0 set bit, 1 → 0001 = 1 set bit, 2 → 0010 = 1 set bit, 3 → 0011 = 2 set bit, 4 → 0100 = 1 set bit ตอนนี้เลือกตัวเลขที่มีบิตเซ็ตเพียง 1 ตัว ได้คือ 1, 2 และ 4
วิธีการที่ใช้ในโปรแกรมด้านล่าง
สามารถมีหลายวิธีในการแก้ปัญหาที่กำหนด คือ วิธีเรียบง่ายและวิธีที่มีประสิทธิภาพ มาดู วิธีเรียบง่าย ก่อน
รับตัวเลขและส่งไปยังฟังก์ชันเพื่อประมวลผลต่อ
ใช้ตัวแปรชั่วคราว count เพื่อเก็บจำนวนตัวเลขในช่วงที่มี set bit เป็น 1 อย่างแม่นยำ
เริ่มลูป FOR จาก i = 1 ถึงตัวเลข
ภายในลูป ตั้งตัวแปร temp ด้วย '__builtin_popcount(i)' ฟังก์ชันที่คืนจำนวน set bit
ตรวจสอบ IF temp == 1 แล้วเพิ่ม count
คืนค่า count
พิมพ์ผลลัพธ์
วิธีที่มีประสิทธิภาพ
รับตัวเลขและส่งไปยังฟังก์ชันเพื่อประมวลผลต่อ
ใช้ตัวแปรชั่วคราว count เพื่อเก็บจำนวนตัวเลขในช่วงที่มี set bit เป็น 1 อย่างแม่นยำ
เริ่มลูป While จาก temp จนกว่า temp <= ตัวเลข
ภายในลูป เพิ่ม count ขึ้น 1 และตั้ง temp = temp * 2
คืนค่า count
พิมพ์ผลลัพธ์
ตัวอย่าง (วิธีเรียบง่าย)
#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
