C++で2つの数値の左端にある異なるビットの位置を求める方法

この問題では、2つの整数 num1 と num2 が与えられ、それぞれを2進数で表したときに初めて値が異なるビット、すなわち最も左側にある相違ビットの位置を求めます。

ビット同士を比較するためには、両者のビット長を揃える必要があります。これには、ビット数が少ない方の数値の先頭に0を補う（桁合わせを行う）方法が用いられます。

入出力例で問題を理解する

入力

num1 = 4, num2 = 7

出力

2

説明

4の2進表現は「100」、7の2進表現は「111」です。

左端のビットはどちらも「1」で一致していますが、左から2番目のビットは「0」と「1」で異なっています。したがって、求める位置は2となります。

解法のアプローチ

この問題を解く一つのアプローチは、まずビット数が少ない方の数値に 2^{(ビット数の差)} を掛ける（＝左シフトする）ことで、両者のビット数を揃えることです。その後、2つの数値のXOR（排他的論理和）を計算すると、ビットが異なる位置だけが1になります。このXOR結果の中で最上位に立っているビットをもとに、「全体のビット数 − XOR結果のビット数 + 1」という式で、左端から数えた相違ビットの位置を求めることができます。

アルゴリズム

ステップ1 ― ビット数が少ない方の数値に 2^(ビット長の差) を掛けて、両者のビット数を揃えます。

ステップ2 ― num1 と num2 のXOR演算を実行します。

ステップ3 ― 相違ビットの位置は「全体のビット数 − XOR結果のビット数 + 1」として求められます。

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

例

#include <iostream>
#include <math.h>
using namespace std;
int findmisMatchBit(int num1, int num2) {
    if (num1 == num2)
        return 0;
    int num1Size = floor(log2(num1)) + 1;
    int num2Size = floor(log2(num2)) + 1;
    int BitSizeDiff = abs(num1Size - num2Size);
    int maxBitSize = max(num1Size, num2Size);
    if (num1Size > num2Size)
        num2 *= pow(2, BitSizeDiff);
    else
        num1 *= pow(2, BitSizeDiff);
    int XOR = num1 ^ num2;
    int XORBitSize = floor(log2(XOR)) + 1;
    return (maxBitSize - XORBitSize + 1);
}
int main() {
    int num1 = 43, num2 = 765;
    cout<<"The position of leftmost dis-similar bit of the two
    number is "<<findmisMatchBit(num1, num2);
    return 0;
}

この例では、43の2進表現は「101011」（6桁）、765の2進表現は「1011111101」（10桁）です。43を4桁分だけ左シフトして桁を揃えた後にXORを取ると、最上位の相違ビットが左から何番目にあるかを計算できます。

出力

The position of leftmost dis-similar bit of the two number is 4