C++での右端のセットビットの位置

この問題では、数値Nが与えられます。私たちのタスクは、数値の右端のセットビットのインデックスを出力することです。

問題を理解するために例を見てみましょう

入力 − 4

出力 − 3

説明 − 4の2進数は100、右端のセットビットのインデックスは3です。

この問題を解決するための簡単な解決策は、設定されたビットに遭遇するまで数値をシフトすることですが、数値が大きい場合、これには多くの計算が必要になる可能性があります。

より効率的な解決策は、ブール代数を使用することです。このために、最初に数値の2の補数を計算します。これにより、数値のすべてのビットが反転し、最初の設定ビットがそのままになります。次に、ビット単位の＆数を計算します。これは2の補数です。これにより、1つのセットビットと必要な位置のみの数値が得られます。解は+1のlog2で与えられます。

これを理解するには少し複雑に思えます。この方法を使用して例を解いてみましょう。

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

例

ソリューションの実装を示すプログラム

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

出力

The rightmost Set bit of the number 10 is : 2