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

Fibbinary Numbers是指在其二进制表示中没有连续的1的数字。然而，它们的二进制表示中可以有连续的零。二进制表示是使用基数2显示数字的表示，只有两个数字1和0。在这里，我们将获得一个数字，并需要确定给定的数字是否是fibbinary数字。

Input 1: Given number: 10
Output: Yes

解释 - 给定数字10的二进制表示是1010，这表明在二进制形式中没有连续的1。

Input 2: Given number: 12
Output: No

解释 − 给定数字的二进制表示是1100，这表明二进制形式中有两个连续的1。

Naive Approach

的中文翻译为：

天真的方法

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

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

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

Example

#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)，因为我们在这里没有使用任何额外的空间。

高效的方法

在之前的方法中，我们逐个检查了每个位，但是还有另一种解决这个问题的方法，那就是位的移动。正如我们所知，在Fibbinary数中，两个连续的位不会同时为1，这意味着如果我们将所有位向左移动一位，那么前一个数和当前数的位在每个位置上将永远不会相同。

例如，

如果我们将给定的数字设为10，那么它的二进制形式将是01010，通过将位移1位，我们将得到数字10100，我们可以看到两个数字在相同位置上都没有1位。

这是斐波那契二进制数的性质，对于数字n和左移n，它们没有相同的位，使得它们的位与运算符为零。

n & (n << 1) == 0

Example

#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)，因为我们在这里没有使用任何额外的空间。

结论

在本教程中，我们已经看到Fibbinary数字是指在其二进制表示中没有连续的1的数字。然而，它们的二进制表示中可以有连续的零。我们在这里实现了两种方法，一种是使用除以2的方法，具有O(log(N))的时间复杂度和O(1)的空间复杂度，另一种是使用左移和位与操作符的属性。

以上是斐波那契二进制数（二进制中没有连续的1）- O(1)方法的详细内容。更多信息请关注PHP中文网其他相关文章！