fibbinary numbers是指在其二进制表示中没有连续的1的数字。然而，它们的二进制表示中可以有连续的零。二进制表示是使用基数2显示数字的表示，只有两个数字1和0。在这里，我们将获得一个数字，并需要确定给定的数字是否是fibbinary数字。
input 1: given number: 10output: yes
解释 - 给定数字10的二进制表示是1010，这表明在二进制形式中没有连续的1。
input 2: given number: 12output: 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)方法的详细内容。