Zählen Sie die Zahlen so, dass eine Zahl die Anzahl der gesetzten Bits als Fibonacci-Zahl haben muss?

Question

In einem Bereich [x, y] finden Sie die Anzahl der Zahlen, so dass eine Zahl die Anzahl der gesetzten Bits als Fibonacci-Zahl haben muss?

Beispiel: [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) 

So Antwort ist 2 (16,17)

Offensichtlich wir die gesetzten Bits zählen und prüfen, ob es eine fibonacci Zahl der Bedingung, ob (5x^2 +/- 4) ist ein perfektes Quadrat mit ..

HINWEIS: es ist eine Interviewfrage. Der Interviewer war mit dem obigen Ansatz nicht zufrieden.

Können wir es besser machen?

Answer 1

Sie können es invertieren und zählen, für jede Fibonacci-Zahl (bis zu einem Limit, werde ich dazu kommen), wie viele Zahlen es "produziert", die in der Reichweite sind.

Sage k ist eine Fibonacci-Zahl (offensichtlich werden Sie nur k versuchen, die Fibonacci-Zahlen sind, die trivial zu erzeugen sind). Wie viele Zahlen gibt es, die k Bits gesetzt haben und zwischen x und y liegen? Nennen Sie dies countBetween(x, y, k). Es ist einfacher, nur bis zu einer Obergrenze zu zählen, also definieren Sie countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k) (unter der Annahme einer exklusiven Obergrenze, die Sie leicht ändern können).

countUpTo(x, k) ist einfach, wenn x eine Potenz von zwei ist, nämlich log(x) nCr k. Wenn x nicht eine Zweierpotenz ist, teilen Sie es dann in zwei Bereiche,

1. die höchste Potenz von zwei weniger als x, q und
2. der Rest x auf.

Der erste Teil bis zu q Sie bereits berechnen kann, hat der zweite Teil einige neue Bereich ein führender 1 und dann die beginnt (nach dem 1 Entfernen) bei 0, so dass Sie countUpTo(x - q, k - 1) berechnen kann.

Dies gibt Ihnen eine rekursive Definition von countUpTo, und vorausgesetzt, Sie a nCr b in weniger als O(a nCr b) Zeit umsetzen können, dieser Algorithmus ist jede Zahl zu vising und testet es nicht gleichwertig.

Wie für das Limit, natürlich können Sie nicht mehr Bits als die Länge der oberen Grenze gesetzt haben, so dass Sie dort aufhören können.

---

Beispiel: countBetween(1024, 1000000, 5) = 15251

Wir brauchen countUpTo(1024, 5) und countUpTo(1000000, 5). countUpTo(1024, 5) ist ein Basisfall, das Ergebnis ist log (1024) nCr 5 = 252.

Für countUpTo(1000000, 5), 1000000 in hexadezimale schreiben, um es leichter zu sehen, was los ist: 0xF4240, die größte Leistung von zwei dort ist natürlich 0x80000, Beitrag log (0x80000) nCr 5 = 11628 und verlassen das Teil von 0x80000 bis 0xF4240. Dieser Teil kann mit countUpTo(0x74240‬, 4) gezählt werden - das obere Bit wird immer in diesem Bereich gesetzt, so dass es von dem Problem durch Anpassen der Grenze und der Anzahl der gesetzten Bits entfernt wird.

Die größte Zweierpotenz in 0x74240 ist 0x40000, was einen Beitrag von log (0x40000) nCr 4 = 3060 ergibt, wobei countUpTo(0x34240‬, 3) übrig bleibt.

Die größte Zweierpotenz in 0x34240 ist 0x20000, was einen Beitrag von log (0x20000) nCr 3 = 680 ergibt, wobei countUpTo(0x14240‬, 2) übrig bleibt.

Die größte Zweierpotenz in 0x14240 ist 0x10000, was einen Beitrag von log (0x10000) nCr 2 = 120 ergibt, was countUpTo(0x4240‬, 1) zurücklässt.

Die größte Zweierpotenz in 0x4240 ist 0x4000, was einen Beitrag von log (0x4000) nCr 1 = 14 ergibt. Dies ergibt countUpTo(0x240‬, 0), was 1 ist, da keine Bits gesetzt werden müssen und es nur eine Möglichkeit gibt, nein zu setzen Bits.

hinzufügen sie alle, 11628 + 3060 + 680 + 120 + 14 + 1 = 15503. subtrahieren 252 von der unteren Grenze und wir bekommen 15251.

Das Beispiel verwendet ziemlich kleine Zahlen, so dass Sie sie leicht überprüfen können, B. durch rohe Gewalt:

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