斐波那契二進位制數（二進位制表示中沒有連續的 1）– O(1) 方法

---

斐波那契二進位制數是指其二進位制表示中沒有連續的 1 的數字。但是，它們的二進位制表示中可以有連續的 0。二進位制表示是指以 2 為底，僅使用 1 和 0 兩個數字來表示數字的表示法。在這裡，我們將給定一個數字，並必須確定給定的數字是否為斐波那契二進位制數。

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)，因為我們在這裡沒有使用任何額外的空間。

高效方法

在先前的方法中，我們檢查了每個位，但還有另一種方法可以解決此問題，即位移。眾所周知，在斐波那契二進位制數中，兩個連續的位不是 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)，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們已經看到斐波那契二進位制數是指其二進位制表示中沒有連續的 1 的數字。但是，它們的二進位制表示中可以有連續的 0。我們在這裡實現了兩種方法，一種是使用除以 2 方法的時間複雜度為 O(log(N))，空間複雜度為 O(1)，另一種是使用左移和按位與運算子的特性。