斐波那契二进制数（二进制表示中没有连续的 1）– O(1) 方法

---

斐波那契二进制数是指其二进制表示中没有连续的 1 的数字。但是，它们的二进制表示中可以有连续的 0。二进制表示是指以 2 为底，仅使用 1 和 0 两个数字来表示数字的表示法。在这里，我们将给定一个数字，并必须确定给定的数字是否为斐波那契二进制数。

Input 1: Given number: 10
Output: Yes

说明 − 给定数字 10 的二进制表示为 1010，这表明其二进制形式中没有连续的 1。

Input 2: Given number: 12
Output: No

说明 − 给定数字的二进制表示为 1100，这表明其二进制形式中存在两个连续的 1。

朴素方法

在这种方法中，我们将使用除法方法来查找每个位，并通过除以 2 来存储前一位以获取所需的信息。我们将使用 while 循环，直到当前数字变为零。

我们将创建一个变量来存储先前找到的位，并将其初始化为零。如果当前位和前一位都是 1，那么我们将返回 false，否则我们将重复，直到完成循环。

完成循环后，我们将返回 true，因为没有找到连续的 1。让我们看看代码 -

示例

#include <iostream>
using namespace std;
bool isFibbinary(int n){
   int temp = n; // defining the temporary number 
   int prev = 0; // defining the previous number 
   while(temp != 0){
      // checking if the previous bit was zero or not
      if(prev == 0){
         // previous bit zero means no need to worry about current 
         prev = temp%2;
         temp /= 2;
      } else {
         // if the previous bit was one and the current is also the same return false
         if(temp%2 == 1){
            return false;
         } else {
            prev = 0;
            temp /=2;
         }
      }
   }
   // return true, as there is no consecutive ones present 
   return true;
}
// main function 
int main(){
   int n = 10; // given number 
   // calling to the function 
   if(isFibbinary(n)){
      cout<<"The given number "<< n<< " is a Fibbinary Number"<<endl;
   } else {
      cout<<"The given number "<< n << " is not a Fibbnary Number"<<endl;
   }
   return 0;
}

输出

The given number 10 is a Fibbinary Number

时间和空间复杂度

上面代码的时间复杂度为 O(log(N))，因为我们正在将当前数字除以 2，直到它变为零。

上面代码的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。

高效方法

在先前的方法中，我们检查了每个位，但还有另一种方法可以解决此问题，即位移。众所周知，在斐波那契二进制数中，两个连续的位不是 1，这意味着如果我们将所有位左移一位，则前一个数字和当前数字的位在每个位置永远不会相同。

例如，

如果我们给定的数字为 10，则其二进制形式将为 01010，通过将位左移 1 位，我们将得到数字 10100，我们可以看到两个数字在相同位置没有 1 位。

这是斐波那契二进制数的一个特性，对于数字 n 和左移 n 位后的数字，它们的任何一位都不相同，这使得它们的按位与运算结果为零。

n & (n << 1) == 0

示例

#include <iostream>
using namespace std;
bool isFibbinary(int n){
   if((n & (n << 1)) == 0){
      return true;
   } else{
      return false;
   }
}
// main function 
int main(){
   int n = 12; // given number 
   // calling to the function 
   if(isFibbinary(n)){
      cout<<"The given number "<< n<< " is a Fibbinary Number"<<endl;
   } else {
      cout<<"The given number "<< n << " is not a Fibbnary Number"<<endl;
   }
   return 0;
}

输出

The given number 12 is not a Fibbnary Number

时间和空间复杂度

上面代码的时间复杂度为 O(1)，因为所有操作都在位级别完成，并且只有两个操作。

上面代码的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。

结论

在本教程中，我们已经看到斐波那契二进制数是指其二进制表示中没有连续的 1 的数字。但是，它们的二进制表示中可以有连续的 0。我们在这里实现了两种方法，一种是使用除以 2 方法的时间复杂度为 O(log(N))，空间复杂度为 O(1)，另一种是使用左移和按位与运算符的特性。