ในปัญหานี้ เราได้รับตัวเลข N หน้าที่ของเราคือพิมพ์ดัชนีของบิตที่ตั้งไว้ทางขวาสุดของตัวเลข
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − 4
ผลผลิต − 3
คำอธิบาย − เลขฐานสองของ 4 คือ 100 ดัชนีของบิตเซ็ตขวาสุดคือ 3
ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ ก็คือการเลื่อนตัวเลขจนกว่าจะพบบิตที่ตั้งไว้ แต่อาจต้องใช้การคำนวณมากหากจำนวนนั้นมาก
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้พีชคณิตแบบบูล สำหรับสิ่งนี้เราจะคำนวณส่วนประกอบ 2 ของตัวเลขก่อน ซึ่งจะพลิกบิตทั้งหมดของตัวเลขออกจากบิตชุดแรกตามที่เป็นอยู่ จากนั้นเราจะคำนวณ bit-wise &ของตัวเลขและเป็นส่วนเสริมของ 2 ซึ่งจะส่งผลให้เป็นตัวเลขที่มีชุดบิตเพียงชุดเดียวและตำแหน่งที่เราต้องการ การแก้ปัญหาจะได้รับจาก log2 ของหมายเลข +1
ดูเหมือนว่าจะซับซ้อนเล็กน้อยที่จะเข้าใจ มาแก้ตัวอย่างโดยใช้วิธีนี้กัน
N= 10 , binary = 1010 2’s complement, 0101 1010 & 0101 = 0010 log2(2) = 1 1+1 = 2 which is the given index.
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <iostream>
#include <math.h>
using namespace std;
void rightSetBit(int N) {
int bitIndex = log2(N & -N)+1;
cout<<bitIndex;
}
int main() {
int N = 10;
cout<<"The rightmost Set bit of the number "<<N<<" is : ";
rightSetBit(N);
return 0;
} ผลลัพธ์
The rightmost Set bit of the number 10 is : 2
