C++で2つの数値の右端の共通ビットの位置を求める方法

問題概要

この問題では、2つの数値 M と N が与えられ、両方の数値に共通して存在するビットの中で、最も右側（下位）にあるものの位置（インデックス）を出力することが求められます。

具体例を使って問題を理解しましょう。

• 入力：N = 4、M = 7
• 出力：3
• 説明：(4)₂ = 100、(7)₂ = 111。共通するビットのうち最も右側にあるものは、3番目の位置に存在します。

解法のアプローチ

この問題を解くには、まず2つの数値で同じ値になっているすべてのビットを見つける必要があります。同じビットを特定するためには、次の手順で考えます。

1. M と N のXOR（排他的論理和）を計算します。XORは「異なるビット」を1とするため、計算結果には差分のあるビットだけが現れます。
2. その結果の否定（NOT）を取ります。これにより、「同じ値になっているビット」だけが1になります。
3. 最後に、その結果における最も右側のセットビット（1になっているビット）の位置を求めます。

少し複雑に感じるかもしれませんので、実際の例で手順を確認してみましょう。

N = 4、M = 7 の場合
~(N^M) = 100

このとき、最も右側のセットビットは3番目の位置にあることがわかります。

実装例

上記の解法をC++で実装したプログラムは以下の通りです。

#include <iostream>
#include <math.h>
using namespace std;
int rightSetBit(int N) {
   int bitIndex = log2(N & -N)+1;
   return bitIndex;
}
void rightSameBit(int m, int n) {
   int diffBit = rightSetBit(~(m^n));
   cout<<diffBit;
}
int main() {
   int N = 4, M = 7;
   cout<<"数値 "<<N<<" と "<<M<<" の最初の右側共通ビットの位置は ";
   rightSameBit(N, M);
   return 0;
}

出力

数値 4 と 7 の最初の右側共通ビットの位置は 3

コードのポイント

rightSetBit 関数では、「N & -N」というビット演算を使用しています。これは2の補数表現の性質を利用したテクニックで、最下位のセットビットだけを取り出すことができます。取り出したビットに対して log2 を計算することで、そのビットの位置（インデックス）を効率的に求められます。

また、rightSameBit 関数では ~(m^n) によって「共通しているビット」のみを抽出し、そこから最も右側のセットビットの位置を取得しています。これにより、O(1)に近い計算量で目的の位置を求めることが可能です。