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)的空间复杂度,另一种是使用左移和位与操作符的属性。