Count numbers so a number should have a bit counter as a fibonacci number?

Question

Given that the range [x, y] finds the number of numbers so that the number should have a bit counter as the fibonacci number?

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

Obviously, we count the bits of the set and check if its number is a fibonacci with the condition that (5x^2 +/- 4) an ideal square.

NOTE : this is an interview question. The interviewer was not satisfied with the above approach.

Can we do better?

Answer 1

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

Say k is the Fibonacci number (obviously, you will try k, which are Fibonacci numbers that are trivial to generate). How many numbers exist that have k bits set and are between x and y? Call it countBetween(x, y, k) . The easiest way is to count only the upper bound, so define countBetween(x, y, k) = countUpTo(y, k) - countUpTo(x, k) (assuming an exceptional upper bound that you can easily change).

countUpTo(x, k) simple when x is a power of two, namely log(x) nCr k . If x not a power of two, then divide it into two ranges,

• the maximum power of two is less than x, q and
• the rest is up to x.

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

This gives you the recursive definition of countUpTo and assumes that you can implement a nCr b less than O(a nCr b) , this algorithm is not equivalent to looking at each number and testing it.

As for the limit, it is obvious that you cannot have more bits 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 the base register, the result is log (1024) nCr 5 = 252.

For countUpTo(1000000, 5) , write 1,000,000 in hexadecimal to make it easier to see what happens: 0xF4240, the largest power of the two in it, of course, 0x80000, logging (0x80000) nCr 5 = 11628 and exiting from 0x80000 up to 0xF4240. This part can be counted using countUpTo(0x74240‬, 4) - the upper bit is always set in this range, so it is removed from the problem by setting the binding and the number of bits set.

The largest power of the two at 0x74240 is 0x40000, which contributes log (0x40000) nCr 4 = 3060, leaving countUpTo(0x34240‬, 3) .

The highest power of the two at 0x34240 is 0x20000, which contributes log (0x20000) nCr 3 = 680, leaving countUpTo(0x14240‬, 2) .

The highest power of the two at 0x14240 is 0x10000, which contributes log (0x10000) nCr 2 = 120, leaving countUpTo(0x4240‬, 1) .

The largest power of the two at 0x4240 is 0x4000, which makes the contribution 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, 11628 + 3060 + 680 + 120 + 14 + 1 = 15503. Subtract 252 from the lower border and get 15251.

The example uses fairly small numbers, so you can easily check them with brute force, for example:

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