Vị trí bit 1 phải nhất trong C++

Trong bài toán này, cho một số N. Nhiệm vụ in chỉ số của bit 1 (set bit) phải nhất của số đó.

Ví dụ minh họa:

Đầu vào - 4

Kết quả - 3

Giải thích - Nhị phân của 4 là 100, chỉ số bit 1 phải nhất là 3.

Để giải bài toán, cách đơn giản là dịch số cho đến khi gặp bit 1 nhưng tốn nhiều tính toán nếu số lớn.

Cách hiệu quả hơn dùng đại số Boole: tính bù 2 của số (flip tất cả bit, giữ bit 1 đầu tiên). Sau đó AND bit-wise của số và bù 2 của nó. Kết quả là số chỉ có một bit 1 tại vị trí cần tìm. Giải pháp là log2 của số + 1.

Ví dụ minh họa:

N = 10, nhị phân = 1010 
Bù 2: 0101 
1010 & 0101 = 0010 
log2(2) = 1 
1+1 = 2 là chỉ số cần tìm.

Chương trình minh họa

#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 << "Bit 1 phải nhất của số " << N << " là: "; 
    rightSetBit(N); 
    return 0; 
}

Kết quả

Bit 1 phải nhất của số 10 là: 2