整数が 2 の累乗ではなく、フィボナッチ数の和として表されると仮定すると、 を100101表しますF(6)+F(3)+F(1)=8+2+1=11( と仮定しF(1)=F(2)=1ます)。O(1) 償却時間で、この表現の下で整数をインクリメントしたいと考えています。
インクリメントのアルゴリズムがあります。直感的には、1 のビットが 2 つ連続してはならないということです。したがって、最初に最下位の 0 ビットを 1 に設定し、次に最上位ビットから始めて、数値に 2 つの連続する 1 ビット、たとえばビット i と i-1 がある場合は、両方を 0 に設定し、i+1 を設定します。 2 つの連続する 1 ビットがなくなるまで、これを再帰的に行います。
私は会計法を使用して償却分析を行います。したがって、インクリメント操作ごとに k ドルを付与し、ビット フリップごとに 1 ドルの費用がかかります。ただし、k の正しい値を設定して証明するのに問題があります。経験的にはうまくいくと思いますk=3が、それを証明する方法がわかりません。
k=3という結論に至るいくつかの命題と観察を次に示します。
アルゴリズムの適用は、1 回のインクリメント ( 0から1まで) と 0 回以上のトリプレット フリップ ( 011から100まで) で構成されます。
アルゴリズムを実行すると、ビット パターン内に11個のパターンがなくなることが保証されます。
増分は、アルゴリズムの開始時に両方とも1ではないため、右端のビットまたはその左のビットのいずれかに適用されます。
インクリメント後、11パターンが一番右またはその 1 つ左の位置に発生する場合があります。両方である可能性がありますが ( 111 )、アルゴリズムは左側を選択します。
フリップは常にこのサブパターン変換を実行します: 011 -> 100、したがって 1 ビットの数はトリプレット フリップごとに減少します。また、トリプリエット フリップの後に残る 1 ビットは、 1である可能性がある右端のビットを除いて、その右側に 0 ビットしかありません(インクリメント フェーズの結果が...111になる場合)。
トリプレット フリップの後、新しい11パターンが出現する可能性がある唯一の場所は、前のパターンの左側の 2 ビット位置です。そのため、左方向に進むトリプレット フリップのカスケードが存在する可能性があります。トリプレットが反転するたびに 1 ビットの数が減少するため、このプロセスは有限です。
値 1 を表すビットにインクリメントが発生するため (右端の 2 ビットで表されるフィボナッチ数はどちらも 1 です)、アルゴリズムは正しいため、表される値は 1 で増加します。フィボナッチ プロパティ。
右端の 2 ビットを除いて、他のすべてのビットは、ある時点でトリプレット フリップの左端のビットになることによってのみ 1 ビットになることができます。
F i +1に対して生成された表現 ( F iは2 より大きいi番目のフィボナッチ数) には、右端のビットを含め、常に 2 つの 1 ビットがあります。これは、おそらく右端のビットを除いて、他のすべてのビットが0であるときに、値F iに対応するビットが設定されるためです。右端のビットが 1 でない場合、アルゴリズムの次の適用時に1になります。したがって、パターン10...01が生成されることが保証され、その値はF i +1です。
0からF i +1になるまでに実行されるインクリメントの数は、明らかにF i +1です。0からF i +1までのトリプレット フリップの回数はF i -1です。これは、インクリメントによってパターン内の1ビットの数が 1 増加するのに対し、トリプリットフリップではこの数が 1 減少するためです。増分数より 2 少ない。
iを増やすと、 F i +1に到達するためのインクリメントとトリプレット フリップの数の比率は1に収束します。これは、2 の差が無視できるようになるためです。これは、問題のkが 3 に収束することを意味します (トリプレット フリップは 3 つのフリップで構成されます)。
アルゴリズムを繰り返し適用するこの JS Fiddleを参照してください。ビット表示、インクリメントとトリプレット フリップの総数、およびそれらの比率が示されています。比率が (非常に) ゆっくりと 1 に収束する様子を確認してください。
上記のフィドルでのアルゴリズムの実装は次のとおりです。
// Apply the algorithm once
var mask;
this.bits |= 1 << (this.bits & 1);
this.increments++;
mask = (this.bits & 6) === 6 ? 4
: (this.bits & 3) === 3 ? 2 : 0;
while (this.bits & mask) {
this.bits ^= mask * 3.5; // 3 flips
mask <<= 2;
this.flips++;
}