は、数字がフィボナッチ数として設定されたビット数を持たなければならないような数を数えますか？

Question

範囲[x、y]を指定すると、フィボナッチ数として設定されたビット数を持つ必要があるような数のカウントが見つかりますか？

例：[15,17]

15 - 1111 - Count of bits is 4 - (4 is not a fibonacci number) 

16 - 10000 - Count of bits is 1 - (1 is a fibonacci number) 

17 - 10001 - Count of bits is 2 - (2 is a fibonacci number) 

そう答える2 (16,17)

明らかに我々は、設定されたビットをカウントし、(5x^2 +/- 4)は完璧な正方形であるかどうかの条件を使用して、そのfibonacci数かどうかをチェックします。..

注：：インタビューの質問です。インタビュアーは上記のアプローチに満足していませんでした。

もっと良いことはできますか？

Answer 1

フィボナッチ数ごとに（それまでは限界に達します）、範囲内に「生成する」数値がいくつあるかを数えます。

と言っています（明らかに、フィボナッチ数であるkを試してみると、生成するのは簡単です）。 kビットが設定され、xとyの間にいくつある数がありますか？このcountBetween(x, y, k)と呼んでください。上限にのみカウントする方が簡単ですので、countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k)（簡単に変更できる上限を前提とします）を定義してください。

countUpTo(x, k)は、xが2の累乗である場合、つまりlog(x) nCr kの場合は単純です。 xが2のべき乗でない場合は、残りの部分は、xまでの二つの範囲、

1. にxより少ない2、qと
2. の最高出力を、それを分割します。

すでに計算することができqまでの最初の部分、第二部は、主要な1と0で（1を削除した後）を開始するので、あなたはcountUpTo(x - q, k - 1)を計算することができ、その後、いくつかの新しい範囲を持っています。

これは、あなたcountUpToの再帰的定義を与え、あなたは以下のO(a nCr b)時間でa nCr bを実装することができると仮定すると、このアルゴリズムは、すべての番号をvisingし、それをテストと同等ではありません。

上限については、明らかに上限の長さよりも多くのビットを設定することはできませんので、ここで停止することができます。

---

例：countBetween(1024, 1000000, 5) = 15251

我々はcountUpTo(1024, 5)とcountUpTo(1000000, 5)を必要としています。 countUpTo(1024, 5)は、それが簡単に何が起こっているのか確認するために作るために16進数で1000000を書き、結果はログ（1024）で、countUpTo(1000000, 5)についてはNCR 5 = 252

基本ケースである：0xF4240、そこに2つの最大のパワーもちろん0x80000であり、log（0x80000）nCr5 = 11628で、0x80000から0xF4240までの部分を残しています。その部分はcountUpTo(0x74240‬, 4)で数えることができます。上位ビットは常にその範囲に設定されているため、ビットとビット数を調整することで問題から削除されます。

0x74240の2の最大の威力は0x40000で、log（0x40000）nCr 4 = 3060の寄与を与え、countUpTo(0x34240‬, 3)のままです。

0x34240の最大の2乗は0x20000で、log（0x20000）nCr 3 = 680の寄与を与え、countUpTo(0x14240‬, 2)のままです。

0x14240の最大の2乗は0x10000であり、log（0x10000）nCr 2 = 120の寄与を与え、countUpTo(0x4240‬, 1)のままです。

0x4240の2の最大の累乗は0x4000であり、log（0x4000）nCr1 = 14の寄与を与えます。これは、設定するビットがなく、noを設定する方法が1つしかないため、countUpTo(0x240‬, 0)を1にしますビット。

下界から+ 680 + 120 + 14 + 1 = 15503.減算252、11628 + 3060をそれらすべてを追加し、あなたがそれらを簡単に確認することができますので、我々は例が適度に小さい数字を使用しています15251.

を取得ブルートフォースによって、例えば：

int count = 0; 
for (int i = 1024; i < 1000000; i++) 
    if (__popcnt(i) == 5) count++; 
std::cout << count << std::endl;