Fibbinary Numbers は、2 進数表現で連続する 1 を持たない数値です。ただし、バイナリ表現では連続したゼロを含めることができます。バイナリ表現は、1 と 0 の 2 桁のみを使用し、基数 2 を使用して数値を表示する表現です。ここでは、数値が与えられ、その数値が 2 進数かどうかを判断する必要があります。
リーリー説明 - 指定された数値 10 のバイナリ表現は 1010 です。これは、バイナリ形式には連続する 1 がないことを示しています。
リーリー説明 -指定された数値のバイナリ表現は 1100 で、バイナリ形式で 2 つの連続する 1 があることを示します。
このメソッドでは、除算メソッドを使用して各ビットを検索し、前のビットを 2 で割って格納し、必要な情報を取得します。現在の数値がゼロになるまで while ループを使用します。
以前に見つけたビットを保存する変数を作成し、それをゼロに初期化します。現在のビットと前のビットの両方が 1 の場合は false が返され、それ以外の場合はループが完了するまで繰り返します。
ループが完了すると、連続する 1 が見つからなかったので true を返します。コードを見てみましょう -
###例### リーリー ###出力### リーリー効率的な方法
前の方法では、ビットを 1 つずつチェックしていましたが、この問題を解決する別の方法があります。それはビットの移動です。フィビナリ数では、連続する 2 つのビットが同時に 1 になることはありません。つまり、すべてのビットを 1 ビット左にシフトすると、前の数値と現在の数値のビットがそれぞれ 1 になります。位置 それは決して同じではありません。
###例えば、###これはフィボナッチ 2 進数の特性です。数値 n と左シフト n は同じビットを持たないため、ビット単位の AND 演算子はゼロになります。
リーリー ###例### リーリー ###出力### リーリー時間と空間の複雑さ
すべての演算がビット レベルで実行され、演算が 2 つしかないため、上記のコードの時間計算量は O(1) です。
ここでは余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。
###結論は###以上がフィボナッチ 2 進数 (2 進数に連続するものはない) - O(1) メソッドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。