เราได้รับตัวเลขหนึ่งตัว ให้เรียกว่า num และงานคือคำนวณจำนวนบิตทั้งหมดที่เปลี่ยนแปลงเมื่อเพิ่ม 1 ให้กับตัวเลข
การแสดงผลแบบไบนารีของตัวเลขทำได้โดยการแปลงตัวเลขที่กำหนดให้อยู่ในรูปของ 0 และ 1 ทำได้หลายวิธี วิธีหนึ่งคือการคำนวณ LCM ของตัวเลขที่กำหนดด้วย 2 และถ้าเศษไม่ใช่ 0 บิตจะตั้งค่าเป็น 1 มิฉะนั้นจะเป็น 0
ตารางการบวกสำหรับบิตคือ
0 + 1 = 1 1 + 0 = 1 0 + 0 = 0 1 + 1 = 1 (มีการขยาย 1 บิต)
ตัวอย่าง
อินพุต – num = 10 เอาต์พุต – count is : 1
คำอธิบาย – การแสดงแบบไบนารีของ 10 คือ 1010 และเมื่อเพิ่ม 1 แล้วจะกลายเป็น 1011 ชัดเจนว่ามีบิตเพียงหนึ่งตัวที่เปลี่ยนแปลง ดังนั้น count คือ 1
อินพุต – num = 5 เอาต์พุต – count is : 2
คำอธิบาย – การแสดงแบบไบนารีของ 5 คือ 101 และเมื่อเพิ่ม 1 แล้วจะกลายเป็น 110 ชัดเจนว่ามีบิตสองตัวที่เปลี่ยนแปลง ดังนั้น count คือ 2
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- รับตัวเลขประเภท integer ให้เป็น int num
- ประกาศตัวแปรเก็บจำนวน ให้เป็น int count
- ใช้ตัวแปรอีกตัวหนึ่ง ให้เป็น temp คำนวณ XOR ของ num และตั้งค่าเป็น n ^ (n + 1)
- ในตัวแปร count เรียก __builtin_popcount(temp) ฟังก์ชันนี้ใช้คำนวณจำนวนบิตที่เป็น 1 ในการแสดงแบบไบนารีของจำนวนเต็ม เป็นฟังก์ชันในตัวของคอมไพเลอร์ GCC
- คืนค่า count
- พิมพ์ผลลัพธ์
ตัวอย่าง
#include <iostream>
using namespace std;
// ฟังก์ชันหาจำนวนบิตที่เปลี่ยน
int changedbit(int n){
int XOR = n ^ (n + 1);
// นับบิตที่เป็น 1 ในค่า XOR
int count = __builtin_popcount(XOR);
return count;
}
int main(){
int n = 10;
cout << "count is: " << changedbit(n);
return 0;
}เอาต์พุต
count is: 1
