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中文網其他相關文章！
