count the numbers such that a number must have its count of set bits as a fibonacci number?

Question

Given a range [x,y] find the count of numbers such that a number must have its count of set bits as a fibonacci number?

Eg: [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 answer is 2 (16,17)

Obviously we count the set bits and check whether its a fibonacci number using the condition whether (5x^2 +/- 4) is a perfect square..

NOTE: it's an interview question. The interviewer wasn't satisfied with the above approach.

Can we do any better?

Answer 1

You can invert it and count, for each Fibonacci number (up to a limit, I'll get to that), how many numbers it "produces" that are in the range.

Say k is a fibonacci number (obviously you will only try k that are Fibonacci numbers, which are trivial to generate). How many numbers are there that have k bits set and are between x and y? Call this countBetween(x, y, k). It's simpler to count up to an upper bound only, so define countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k) (assuming exclusive upper bound which you can easily change).

countUpTo(x, k) is simple when x is a power of two, namely log(x) nCr k. If x isn't a power of two, then split it into two ranges,

1. the highest power of two less than x, q and
2. the rest up to x.

The first part up to q you can already calculate, the second part has a leading 1 and then some new range that starts (after removing the 1) at 0, so you can calculate countUpTo(x - q, k - 1).

This gives you a recursive definition of countUpTo, and assuming you can implement a nCr b in less than O(a nCr b) time, this algorithm is not equivalent to vising every number and testing it.

As for the limit, obviously you cannot have more bits set than the length of the upper bound, so you can stop there.

---

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

We need countUpTo(1024, 5) and countUpTo(1000000, 5). countUpTo(1024, 5) is a base case, the result is log(1024) nCr 5 = 252.

For countUpTo(1000000, 5), write 1000000 in hexadecimal to make it easier to see what's going on: ‭0xF4240‬, the biggest power of two in there is of course 0x80000, contributing log(0x80000) nCr 5 = 11628 and leaving the part from 0x80000‬ up to 0xF4240‬. That part can be counted with countUpTo(0x74240‬, 4) - the upper bit is always set in that range, so it is removed from the problem by adjusting the bound and the number of set bits.

The biggest power of two in 0x74240‬ is 0x40000, giving a contribution of log(0x40000) nCr 4 = 3060, leaving countUpTo(0x34240‬, 3).

The biggest power of two in 0x34240‬ is 0x20000, giving a contribution of log(0x20000) nCr 3 = 680, leaving countUpTo(0x14240‬, 2).

The biggest power of two in 0x14240‬ is 0x10000, giving a contribution of log(0x10000) nCr 2 = 120, leaving countUpTo(0x4240‬, 1).

The biggest power of two in 0x4240‬ is 0x4000, giving a contribution of log(0x4000) nCr 1 = 14. This leaves countUpTo(0x240‬, 0) which is 1 because there are no bits to set and there is only one way to set no bits.

Add them all up, 11628 + 3060 + 680 + 120 + 14 + 1 = 15503. Subtract 252 from the lower bound and we get 15251.

The example uses reasonably small numbers so you can easily verify them by brute force, for example:

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