C++で2つの数値の右端から最初に異なるビットの位置を求める方法

問題の概要

この問題では、2つの整数 N と M が与えられます。目的は、それぞれの数値を2進数で表したときに、右側(最下位ビット側)から見て最初に異なるビットが現れる位置(インデックス)を求めることです。

具体例

• 入力: N = 12、M = 10
• 出力: 2
• 説明: (12)₁₀ = (1100)₂、(10)₁₀ = (1010)₂。右から2番目のビットだけが異なっています。

解き方の考え方:XORを活用する

2つの数値の「異なるビット」をすべて見つけるには、XOR(排他的論理和) を使うのが最も効果的です。XORは対応するビットが異なる場合にのみ1を返すため、N ^ M の結果には「異なるすべてのビット」が1として現れます。

あとは、その結果(N ^ M)の中で最も右側にあるセットされたビット(1になっているビット)の位置を特定すればよいことになります。

N = 12 , M = 10
N^M = 0110

この例では、右端のセットされたビットはインデックス2の位置に存在します。

右端のセットビットを求めるテクニック

任意の整数 x に対して x & -x を計算すると、x の中で最も下位にあるセットビットだけが残ります。これは2の補数表現の性質を利用した有名なビットトリックです。さらにこれに log2 を適用すれば、そのビットの指数(0始まりの位置)が得られるため、+1 することで1始まりのインデックスに変換できます。

実装例(C++)

上記のアプローチを実装したプログラムがこちらです。

#include <iostream>
#include <math.h>
using namespace std;

int rightSetBit(int N) {
    int bitIndex = log2(N & -N) + 1;
    return bitIndex;
}

void rightDiffBit(int m, int n) {
    int diffBit = rightSetBit(m^n);
    cout << diffBit;
}

int main() {
    int N = 12, M = 10;
    cout << "Postion of first right different bit of the number " << N << " & " << M << " is ";
    rightDiffBit(N, M);
    return 0;
}

出力

Postion of first right different bit of the number 12 & 10 is 2

まとめ

この解法のポイントは次の2つです。

• N ^ M によって「異なるビットだけが立った数」を作り出す
• N & -N と log2 を組み合わせて、最下位のセットビットの位置を効率的に求める

各ビットをループで順番に比較する方法と比べ、ビット演算を組み合わせることでコードが簡潔になり、より高速に答えを得ることができます。