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 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 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)方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444852.html
微信扫一扫 
支付宝扫一扫 
