斐波那契数（二进制中没有连续的 1）——O(1) 方法
斐波那契数是二进制表示中没有连续 1 的数字。但是，它们的二进制表示中可以有连续的零。二进制表示法是以 2 为基数且只有 1 和 0 两个数字的表示法。在这里，我们将给出一个数字，并且必须确定给定的数字是否是二进制数。
输入 1：给定数字：10 输出：是
解释 - 给定数字 10 的二进制表示形式为 1010，这表明二进制形式中没有连续的数字。
输入 2：给定数字：12 输出：否
解释 - 给定数字的二进制表示形式为 1100，这表明二进制形式中有两个连续的数字。
简单方法
在这种方法中，我们将使用除法查找每个位，并通过除以 2 来存储前一位以获取所需信息。我们将使用 while 循环，直到当前数字变为零。
我们将创建一个变量来存储先前找到的位，并将其初始化为零。如果当前位和前一个位都是 1，则我们将返回 false，否则我们将重复，直到完成循环。
完成循环后，我们将返回 true，因为没有找到连续的位。让我们看看代码 -
示例
#include <iostream>
using namespace std;
bool isFibbinary(int n){
int temp = n; // 定义临时数字
int prev = 0; // 定义前一个数字
while(temp != 0){
// 检查前一位是否为零
if(prev == 0){
// 前一位为零意味着无需担心当前
prev = temp%2;
temp /= 2;
} else {
// 如果前一位为 1，且当前位也为 1，则返回 false
if(temp%2 == 1){
return false;
} else {
prev = 0;
temp /=2;
}
}
}
// v
return true;
}
// main 主函数
int main(){
int n = 10; // 给定数字
// 调用函数
if(isFibbinary(n)){
cout<<"给定数字 "<< n<< " 是斐波那契数"<<endl;
} else {
cout<<"给定数字 "<< n << " 不是斐波那契数"<<endl;
}
return 0;
}
输出
给定的数字 10 是一个斐波那契数
时间和空间复杂度
上述代码的时间复杂度为 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 主函数
int main(){
int n = 12; // 给定数字
// 调用函数
if(isFibbinary(n)){
cout<<"给定数字 "<< n<< " 是斐波那契数"<<endl;
} else {
cout<<"给定数字 "<< n << " 不是斐波那契数"<<endl;
}
return 0;
}
输出
给定的数字 12 不是斐波那契数
时间和空间复杂度
上述代码的时间复杂度为 O(1)，因为所有操作都是在位级别完成的，而且只有两个操作。
上述代码的空间复杂度为 O(1)，因为我们这里没有使用任何额外的空间。
结论
在本教程中，我们已经看到斐波那契数是二进制表示中没有连续 1 的数字。但是，它们的二进制表示中可以有连续的零。我们在这里实现了两种方法，一种是使用除以 2 的方法，时间复杂度为 O(log(N))，空间复杂度为 O(1)，第二种是使用左移和按位与运算符的属性。
