Vị trí bit 1 thứ K trong số nguyên trong C++

Trong bài toán này, cho hai số nguyên N và K. Nhiệm vụ tìm chỉ số của bit 1 (set bit) thứ K của số N, đếm từ phải sang trái.

Bit 1 được kiểm tra từ biểu diễn nhị phân của số. Chỉ số trong nhị phân bắt đầu từ 0 ở bên phải và lan sang trái.

Ví dụ - trong số nhị phân '011101', tại chỉ số 0 từ phải là 1, chỉ số 1 là 0, v.v.

Ví dụ minh họa:

Đầu vào - N = 6, K = 2

Kết quả - 2

Giải thích - Nhị phân của 6 là 0110. Bit 1 thứ 2 từ phải ở chỉ số 2.

Để giải bài toán, kiểm tra bit hiện tại có phải 1 không, nếu có giảm K. Sau mỗi kiểm tra, dịch số sang phải 1 bit (để lấy bit tiếp theo), đồng thời đếm số lần dịch. Khi K bằng 0, in số lần dịch.

Chương trình minh họa

#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 << "Bit 1 thứ " << K << " của số " << N << " ở chỉ số: \t"; 
    int index = FindIndexKthBit(N, K); 
    if (index != -1) 
        cout << index; 
    else 
        cout << "\nKhông tìm thấy chỉ số"; 
    return 0; 
}

Kết quả

Bit 1 thứ 2 của số 12 ở chỉ số: 3