ตำแหน่งบิตขวาสุดที่เซ็ตใน C++

ในปัญหานี้ เราได้รับตัวเลข N งานของเราคือพิมพ์ดัชนีของบิตขวาสุดที่เซ็ตของตัวเลข

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - 4

Output - 3

Explanation - ไบนารีของ 4 คือ 100 ดัชนีของบิตขวาสุดที่เซ็ตคือ 3

เพื่อแก้ปัญหานี้ วิธีแก้ง่ายๆ จะเป็นการ shift ตัวเลขจนกว่าจะพบบิตเซ็ต แต่สิ่งนี้อาจใช้การคำนวณมากหากตัวเลขใหญ่

วิธีแก้ที่มีประสิทธิภาพมากกว่าจะใช้พีชคณิตบูลีน สำหรับสิ่งนี้ เราจะคำนวณ 2's complement ของตัวเลขก่อน ซึ่งจะพลิกบิตทั้งหมดของตัวเลขทิ้งบิตเซ็ตแรกไว้เหมือนเดิม จากนั้นเราจะคำนวณ bit-wise AND ของตัวเลขและ 2's complement ของมัน สิ่งนี้จะทำให้ได้ตัวเลขที่มีบิตเซ็ตเพียงบิตเดียวและตำแหน่งที่เราต้องการ คำตอบจะได้จาก log2 ของตัวเลข + 1

สิ่งนี้ดูซับซ้อนเล็กน้อย มาแก้ตัวอย่างด้วยวิธีนี้:

N = 10 , binary = 1010
2's complement, 0101
1010 & 0101 = 0010
log2(2) = 1
1+1 = 2 ซึ่งคือดัชนีที่กำหนด

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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