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。
在这种方法中，我们将使用除法方法来找到每一位，并通过除以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)，因为我们在这里没有使用任何额外的空间。
在之前的方法中，我们逐个检查了每个位，但是还有另一种解决这个问题的方法，那就是位的移动。正如我们所知，在Fibbinary数中，两个连续的位不会同时为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)，因为我们在这里没有使用任何额外的空间。
在本教程中，我们已经看到Fibbinary数字是指在其二进制表示中没有连续的1的数字。然而，它们的二进制表示中可以有连续的零。我们在这里实现了两种方法，一种是使用除以2的方法，具有O(log(N))的时间复杂度和O(1)的空间复杂度，另一种是使用左移和位与操作符的属性。
以上是斐波那契二进制数（二进制中没有连续的1）- O(1)方法的详细内容。更多信息请关注PHP中文网其他相关文章！
