Trong bài toán này, chúng ta được cung cấp hai số nguyên N và K. Nhiệm vụ của chúng ta là tìm chỉ số của K th đặt một chút của số N, được tính từ bên phải.
Các bit đặt được kiểm tra từ biểu diễn nhị phân của số. Việc lập chỉ mục trong biểu diễn nhị phân bắt đầu từ chỉ mục 0 từ hướng bên phải và lan truyền sang trái.
Ví dụ - trong số nhị phân ‘011101’, tại chỉ mục 0 từ bên phải chúng ta có 1, tại chỉ mục 1 từ bên phải chúng ta có 0, v.v.
Bây giờ, hãy lấy một ví dụ để hiểu vấn đề
Đầu vào - N =6, K =2
Đầu ra - 2
Giải thích - Biểu diễn nhị phân của 6 là 0110. Bit đặt thứ 2 từ bên phải sẽ ở chỉ số 2.
Để giải quyết vấn đề này, chúng ta sẽ phải kiểm tra xem bit hiện tại đã được đặt chưa, nếu đúng thì chúng ta sẽ giảm giá trị của K. Sau mỗi lần kiểm tra, chúng ta sẽ chuyển số bt 1, điều này sẽ cho bit tiếp theo, chúng ta cũng vậy. sẽ duy trì số ca đã làm. Khi giá trị của K trở thành 0, chúng tôi sẽ in số ca đã thực hiện.
Ví dụ
Chương trình thể hiện việc triển khai logic của chúng tôi
#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;
} Đầu ra
The 2th set bit of the number 12 is at index : 3