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

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)的空間複雜度，另一種是使用左移和位與操作符的屬性。

以上是斐波那契二進制數（二進制中沒有連續的1）- O(1)方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！