เราได้รับตัวเลข สมมติว่า num และภารกิจคือการคำนวณจำนวนบิตทั้งหมดที่เปลี่ยนแปลงเมื่อเพิ่ม 1 ลงในตัวเลข
การแสดงเลขฐานสองของตัวเลขทำได้โดยการแปลงตัวเลขที่กำหนดให้อยู่ในรูปของ 0 และ 1 และทำได้ด้วยวิธีการต่างๆ ในวิธีหนึ่ง เราคำนวณ LCM ของตัวเลขที่กำหนดด้วย 2 และหากตัวเตือนไม่ใช่ 0 บิตจะถูกตั้งค่าเป็น 1 มิฉะนั้นจะถูกตั้งค่าเป็น 0
ตารางเพิ่มเติมสำหรับบิตคือ
0 + 1 = 1 1 + 0 = 1 0 + 0 = 0 1 + 1 = 1 ( 1 bit carry)
ตัวอย่าง
Input − num = 10 Output − count is : 1
คำอธิบาย − การแทนค่าไบนารีของ 10 คือ 1010 และเมื่อเพิ่ม 1 เข้าไป การแทนค่าจะกลายเป็น 1011 เห็นได้ชัดว่ามีการเปลี่ยนแปลงเพียงบิตเดียวเท่านั้น ดังนั้นการนับจึงเป็น 1
Input − num = 5 Output − count is : 2
คำอธิบาย − การแทนค่าไบนารีของ 5 คือ 101 และเมื่อเพิ่ม 1 เข้าไป การแทนค่าจะกลายเป็น 110 เห็นได้ชัดว่ามีการเปลี่ยนแปลงสองบิต ดังนั้นการนับจึงเป็น 2
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ใส่จำนวนชนิดจำนวนเต็ม สมมุติว่า int num
-
ประกาศตัวแปรที่จะเก็บการนับ สมมติว่า int count
-
ใช้ตัวแปรอื่น สมมุติว่า temp ที่จะคำนวณ XOR ของ num และตั้งค่าเป็น n ^ (n + 1)
-
ในการเรียกตัวแปรการนับ __builtin_popcount(temp) ฟังก์ชันนี้คือการคำนวณจำนวนตัวเลขในการแทนค่าเลขฐานสองจำนวนเต็มที่กำหนด เป็นฟังก์ชัน inbuilt ของคอมไพเลอร์ GCC
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#include <iostream>
using namespace std;
// Function to find number of changed bit
int changedbit(int n){
int XOR = n ^ (n + 1);
// Count set bits in xor value
int count = __builtin_popcount(XOR);
return count;
}
int main(){
int n = 10;
cout <<"count is: " <<changedbit(n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
count is: 1
