计算数字，这样一个数字必须将其设置位的计数作为斐波那契数？

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

你可以反转它并计算，对于每个斐波那契数（达到一个极限，我会达到那个），有多少个数字在范围内"produces"。

假设 k 是一个斐波那契数（显然你只会尝试 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的两个的最高次方，q和
剩下的 x。

您已经可以计算到 q 的第一部分，第二部分有一个前导 1，然后是一些从 0 开始（删除 1 后）的新范围，因此您可以计算 countUpTo(x - q, k - 1).

这为您提供了 countUpTo 的递归定义，假设您可以在不到 O(a nCr b) 的时间内实现 a nCr b，则此算法不等同于查看每个数字并对其进行测试.

至于限制，显然你不能设置比上限长度更多的位，所以你可以到此为止。

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

我们需要 countUpTo(1024, 5) 和 countUpTo(1000000, 5)。 countUpTo(1024, 5) 是基本情况，结果是 log(1024) nCr 5 = 252.

对于countUpTo(1000000, 5)，把1000000写成16进制，方便看情况：0xF4240，里面的2的最大幂当然是0x80000，贡献log(0x80000) nCr 5 = 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) nCr 1 = 14。这剩下 countUpTo(0x240‬, 0) 为 1，因为没有要设置的位，只有一种不设置位的方法。

全部相加，11628 + 3060 + 680 + 120 + 14 + 1 = 15503。下限减去252，得到15251。

该示例使用相当小的数字，因此您可以轻松地通过暴力验证它们，例如：

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

计算数字，这样一个数字必须将其设置位的计数作为斐波那契数？

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

algorithm

bit-manipulation

fibonacci