计算数字,使得一个数字必须将其设定位数作为斐波纳契数？

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)

显然我们计算设置位并检查它是否fibonacci使用条件是否(5x^2 +/- 4)是一个完美的正方形.

注意:这是一个面试问题.面试官对上述方法不满意.

我们可以做得更好吗？

Answer 1

您可以对每个Fibonacci数进行反转并计数(达到极限,我会得到它),它产生的数量在该范围内.

假设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的幂,则将其分成两个范围,

1. 两个小于x的最高功率,q和
2. 剩下的就是x.

第一部分高达q你已经可以计算出,第二部分具有领先1,然后从0开始(除去1后),这样你就可以计算出一些新的范围countUpTo(x - q, k - 1).

这为您提供了递归定义countUpTo,并假设您可以a nCr b在不到O(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以便更容易看到发生了什么:0xF4240,当然有两个中最大的2的幂当然是0x80000,贡献log(0x80000)nCr 5 = 11628并且将部分从0x80000保留到0xF4240.该部分可以计数countUpTo(0x74240?, 4)- 高位始终设置在该范围内,因此通过调整设置位的边界和数量将其从问题中移除.

0x74240中两个的最大功率是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中两个的最大功率是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;