1. 序章

数値のバイナリギャップは、数値のバイナリ表現で2つのゼロの間に発生する連続するゼロの最大数として定義されます。 この問題は繰り返し解決できますが、この記事では再帰的な解決策を紹介します。

2. 解決

2.1. アルゴリズム

問題について考えてみましょう。 まず、数値のビットを少しずつ抽出する方法を見つける必要があります。 次に、1に等しい最初のビットが見つかった場合にのみ、連続するゼロの数のカウントを開始できることに気付くことができます。 これを行う方法は、3つの変数を渡すだけです。

  • Number ：この問題を解決するための数値
  • FoundFirstOne ：最初のアクティブビットが見つかるとtrueに設定されるブール変数
  • NumOfZeros ：これまでの連続ゼロの数

数値から最下位ビットを抽出するには、2で割った余りを取ります。 同様に、数値から最下位ビットを削除するには、それを2で割る必要があります。 結果として、数値からビットを抽出するたびに、2つのオプションがあります。

  • 抽出されたビットが1に等しい場合は、数値を2で割った後、アルゴリズムを再帰的に呼び出す必要があります。 また、FoundFirstOneをtrueに設定する必要があります（まだ設定されていない場合）。 最後に、 NumOfZerosをゼロに設定する必要があります。これは、現在、連続するゼロがないためです。 また、次のビットがゼロに等しい場合に備えて、カウントを再開する必要があります。
  • 抽出されたビットがゼロに等しい場合は、数値を2で割った後、アルゴリズムを再帰的に呼び出す必要があります。 ただし、この場合、FoundFirstOneの値は変更されません。 また、 FoundFirstOneがtrueに等しい場合にのみ、NumOfZerosを1つ増やす必要があります。

各ステップで、NumOfZerosと再帰呼び出しから返された値の間の最大値を返します。 ただし、この数値がゼロに等しい場合、アルゴリズムはすぐにゼロを返す必要があります。これは、最後のビットが1であり、この呼び出しで連続するゼロが見つからなかったことを示します。

2.2. 擬似コード

今説明したアルゴリズムの背後にある考え方は、最初の1ビットを見つけた後にのみ連続するゼロのカウントを開始できるということです。 最初の1ビットが見つかったら、連続するゼロの数を1つ増やすか、現在のビットが1に等しい場合はゼロに設定します。 再帰呼び出しが終了すると、答えは再帰的に検出された値か、これまでに得られた連続するゼロの数のいずれかになります。

再帰的アルゴリズムの疑似コードを見てみましょう。

このアルゴリズムの最初の呼び出しでは、数値を渡し、FoundFirstOneをfalseに設定し、NumOfZerosの値をゼロに設定する必要があります。

2.3. 複雑

再帰アルゴリズムの複雑さはO（Log2N）です。これは、アルゴリズムが再帰呼び出しを1回だけ行うため、数値を2で除算するためです。 これは、アルゴリズムが合計Log2Nステップを実行することを意味します。

3. 結論

この記事では、バイナリギャップ問題を解決するための再帰的アルゴリズムについて説明しました。

最初に、アルゴリズムがどのように機能するかを説明しました。 次に、アルゴリズムの擬似コードを示し、最後にアルゴリズムの複雑さを示しました。