ตำแหน่งของ K-th Set Bit ในตัวเลขใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มสองตัว N และ K งานของเราคือหาดัชนีของ K^th set bit ของตัวเลข N นับจากขวา

Set bits ถูกตรวจสอบจากการแทนค่าไบนารีของตัวเลข การจัดดัชนีในการแทนค่าไบนารีเริ่มจากดัชนี 0 จากทิศทางขวาและแพร่กระจายไปทางซ้าย

ตัวอย่าง - ในตัวเลขไบนารี '011101' ที่ดัชนี 0 จากขวาเราได้ 1 ที่ดัชนี 1 จากขวาเราได้ 0 และไปเรื่อยๆ

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

Input - N = 6, K = 2

Output - 2

Explanation - การแทนค่าไบนารีของ 6 คือ 0110 บิตเซ็ตตัวที่ 2 จากขวาจะอยู่ที่ดัชนี 2

เพื่อแก้ปัญหานี้ เราจะต้องตรวจสอบว่าบิตปัจจุบันเป็นเซ็ตหรือไม่ หากเป็น เราจะลดค่า K ลง หลังจากการตรวจสอบแต่ละครั้ง เราจะ shift ตัวเลข 1 บิต ซึ่งจะให้บิตถัดไป นอกจากนี้เรายังรักษาจำนวนการ shift ที่ทำไป เมื่อค่า K กลายเป็น 0 เราจะพิมพ์จำนวนการ shift ที่ทำ

ตัวอย่าง

โปรแกรมแสดงการนำตรรกะของเราไปใช้งาน:

#include <iostream>
using namespace std;

int FindIndexKthBit(int N, int K) {
    int index = 0;
    while (N) {
        if (N & 1)
            K--;
        if (!K)
            return index;
        index++;
        N = N >> 1;
    }
    return -1;
}

int main() {
    int N = 12, K = 2;
    cout << "The " << K << "th set bit of the number " << N << " is at index : \t";
    int index = FindIndexKthBit(N, K);
    if (index != -1)
        cout << index;
    else
        cout << "\nsorry no index found";
    return 0;
}

ผลลัพธ์

The 2th set bit of the number 12 is at index : 3