Vị trí của bit đặt ngoài cùng bên phải trong C ++

Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là in chỉ mục của bit tập hợp ngoài cùng bên phải của số.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - 4

Đầu ra - 3

Giải thích - nhị phân của 4 là 100, chỉ số của bit đặt ngoài cùng bên phải là 3.

Để giải quyết vấn đề này, một giải pháp đơn giản sẽ là chuyển số cho đến khi gặp một bit đã đặt nhưng điều này có thể mất nhiều tính toán nếu số lớn.

Một giải pháp hiệu quả hơn sẽ là sử dụng đại số boolean. Đối với điều này, trước tiên, chúng tôi sẽ tính toán phần bù của 2 của số, điều này sẽ lật tất cả các bit của số để lại bit đặt đầu tiên như cũ. Sau đó, chúng tôi sẽ tính toán bit-khôn &của số và nó là phần bổ sung của 2. Điều này sẽ dẫn đến một số chỉ có một bit được đặt và vị trí mà chúng ta muốn. Giải pháp sẽ được đưa ra bởi log2 của số +1.

Điều này có vẻ hơi phức tạp để hiểu, hãy giải quyết một ví dụ bằng phương pháp này.

N= 10 , binary = 1010
2’s complement, 0101
1010 & 0101 = 0010
log2(2) = 1
1+1 = 2 which is the given index.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

The rightmost Set bit of the number 10 is : 2