フィボナッチ 2 進数 (2 進数に連続するものはない) - O(1) メソッド

Fibbinary Numbers は、2 進数表現で連続する 1 を持たない数値です。ただし、バイナリ表現では連続したゼロを含めることができます。バイナリ表現は、1 と 0 の 2 桁のみを使用し、基数 2 を使用して数値を表示する表現です。ここでは、数値が与えられ、その数値が 2 進数かどうかを判断する必要があります。

説明 - 指定された数値 10 のバイナリ表現は 1010 です。これは、バイナリ形式には連続する 1 がないことを示しています。

説明 -指定された数値のバイナリ表現は 1100 で、バイナリ形式で 2 つの連続する 1 があることを示します。

素朴なアプローチ

素朴なアプローチ

このメソッドでは、除算メソッドを使用して各ビットを検索し、前のビットを 2 で割って格納し、必要な情報を取得します。現在の数値がゼロになるまで while ループを使用します。

以前に見つけたビットを保存する変数を作成し、それをゼロに初期化します。現在のビットと前のビットの両方が 1 の場合は false が返され、それ以外の場合はループが完了するまで繰り返します。

ループが完了すると、連続する 1 が見つからなかったので true を返します。コードを見てみましょう -

時間と空間の複雑さ

現在の数値をゼロになるまで 2 で割るので、上記のコードの時間計算量は O(log(N)) です。

ここでは余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

効率的な方法

前の方法では、ビットを 1 つずつチェックしていましたが、この問題を解決する別の方法があります。それはビットの移動です。フィビナリ数では、連続する 2 つのビットが同時に 1 になることはありません。つまり、すべてのビットを 1 ビット左にシフトすると、前の数値と現在の数値のビットがそれぞれ 1 になります。位置 それは決して同じではありません。

与えられた数値を 10 とすると、そのバイナリ形式は 01010 になります。ビットを 1 ビットシフトすると、数値 10100 が得られます。両方の数値に 1 ビットがないことがわかります。位置 。

これはフィボナッチ 2 進数の特性です。数値 n と左シフト n は同じビットを持たないため、ビット単位の AND 演算子はゼロになります。

時間と空間の複雑さ

すべての演算がビット レベルで実行され、演算が 2 つしかないため、上記のコードの時間計算量は O(1) です。

ここでは余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

このチュートリアルでは、フィバイナリ数値とは、バイナリ表現で連続する 1 を持たない数値であることを説明しました。ただし、バイナリ表現では連続したゼロを含めることができます。ここでは 2 つのメソッドを実装しました。1 つは、時間計算量が O(log(N)) で空間計算量が O(1) の 2 による除算方法を使用するもので、もう 1 つは左シフトとビット単位を使用するものです。 AND 演算子の。

以上がフィボナッチ 2 進数 (2 進数に連続するものはない) - O(1) メソッドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。