计算Fibonacci数系统中设置的位数？

Question

我们知道,每个非负十进制数可以用Fibonacci数的和来唯一表示(这里我们关注最小表示,即在数字的表示中没有连续的Fibonacci数,并且每个Fibonacci数最多只取一个在代表中).

例如:

1->  1
2-> 10
3->100
4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);

所以每个十进制数可以在Fibonacci系统中表示为二进制序列.如果我们在Fibonacci系统中连续写出所有自然数,我们将获得如下序列:110100101 ...这称为"自然数的斐波那契位序列".

我的任务是计算第1位出现在该序列的前N位中的次数.由于N可以取1到10 ^ 15的值,我可以不存储斐波纳契数列吗？

例如:如果N是5,答案是3.

Answer 1

这是 O((log n)^3)。

让我们计算前 N 位可以容纳多少个数字

想象一下我们有一个函数：

long long number_of_all_bits_in_sequence(long long M); 

它计算由所有不大于 M 的数字创建的“自然数斐波那契位序列”的长度。

通过这个函数，我们可以使用二分查找来查找前 N 位适合多少个数字。

前 M 个数字有多少位是 1

让我们创建一个函数来计算有多少个 <= M 的数字在第 k 位处为 1。

long long kth_bit_equal_1(long long M, int k);

首先让我们针对所有小值预处理此函数的结果，假设 M <= 1000000。

M > PREPROCESS_LIMIT 的实现：

long long kth_bit_equal_1(long long M, int k) {
   if (M <= PREPROCESS_LIMIT) return preprocess_result[M][k];

   long long fib_number = greatest_fib_which_isnt_greater_than(M);
   int fib_index = index_of_fib_in_fibonnaci_sequence(fib);

   if (fib_index < k) {
      // all numbers are smaller than k-th fibbonacci number
      return 0;
   }

   if (fib_index == k) {
      // only numbers between [fib_number, M] have k-th bit set to 1
      return M - fib_number + 1;       
   } 

   if (fib_index > k) {
      long long result = 0;

      // all numbers between [fib_number, M] have bit at fib_index set to 1
      // so lets subtrack fib_number from all numbers in this interval
      // now this interval is [0, M - fib_number]
      // lets calculate how many numbers in this inteval have k-th bit set.
      result += kth_bit_equal_1(M - fib_number, k);

      // don't forget about remaining numbers (interval [1, fib_number - 1])
      result += kth_bit_equal_1(fib_number - 1, k);

      return result;
   }
}

该函数的复杂度为 O(M / PREPROCESS_LIMIT)。

请注意，重复出现的加数之一始终是斐波那契数之一。

kth_bit_equal_1(fib_number - 1, k);

因此，如果我们记住所有计算结果，那么复杂性将提高到 T(N) = T(N/2) + O(1) 。T(n) = O(log N)。

让我们回到 number_of_all_bits_in_sequence

我们可以稍微修改 kth_bit_equal_1，这样它也会计算等于 0 的位。