Heim > Artikel > Backend-Entwicklung > Fibonacci-Binärzahlen (keine aufeinanderfolgenden Einsen im Binärformat) – O(1)-Methode
Fibbinäre Zahlen sind Zahlen, die in ihrer binären Darstellung keine aufeinanderfolgenden Einsen haben. Allerdings können sie in ihrer binären Darstellung aufeinanderfolgende Nullen haben. Die binäre Darstellung ist eine Darstellung, die Zahlen zur Basis 2 mit nur zwei Ziffern 1 und 0 anzeigt. Hier erhalten wir eine Zahl und müssen feststellen, ob es sich bei der angegebenen Zahl um eine fibbinäre Zahl handelt.
Input 1: Given number: 10 Output: Yes
Erklärung – Die binäre Darstellung der gegebenen Zahl 10 ist 1010, was zeigt, dass es in der binären Form keine aufeinanderfolgenden Einsen gibt.
Input 2: Given number: 12 Output: No
Erläuterung − Die binäre Darstellung der angegebenen Zahl ist 1100, was darauf hinweist, dass es in der binären Form zwei aufeinanderfolgende Einsen gibt.
Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.Nach Abschluss der Schleife geben wir true zurück, da keine aufeinanderfolgende 1 gefunden wurde. Werfen wir einen Blick auf den Code −
Beispiel
#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; }
Ausgabe
The given number 10 is a Fibbinary Number
Effiziente Methode
Bei der vorherigen Methode haben wir jedes Bit einzeln überprüft, aber es gibt eine andere Möglichkeit, dieses Problem zu lösen, und das ist die Bitverschiebung. Da wir wissen, dass in fibbinären Zahlen zwei aufeinanderfolgende Bits nicht gleichzeitig 1 sind, bedeutet dies, dass, wenn wir alle Bits um ein Bit nach links verschieben, die Bits der vorherigen Zahl und der aktuellen Zahl jeweils gleich sind Position Es wird nie mehr dasselbe sein.
Wenn wir die gegebene Zahl als 10 annehmen, dann ist ihre Binärform 01010. Durch Verschieben des Bits um 1 Bit erhalten wir die Zahl 10100. Wir können sehen, dass beide Zahlen nicht 1 Bit an derselben Position haben.
Dies ist die Eigenschaft von Fibonacci-Binärzahlen. Für die Zahl n und die Linksverschiebung n haben sie nicht die gleichen Bits, sodass ihr bitweiser UND-Operator Null ist.
n & (n << 1) == 0
Beispiel
#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; }
Ausgabe
The given number 12 is not a Fibbnary Number
Fazit
In diesem Tutorial haben wir gesehen, dass eine Fibbinärzahl eine Zahl ist, die in ihrer binären Darstellung keine aufeinanderfolgenden Einsen hat. Allerdings können sie in ihrer binären Darstellung aufeinanderfolgende Nullen haben. Wir haben hier zwei Methoden implementiert: Eine verwendet die Methode „Teilen durch 2“, die eine zeitliche Komplexität von O (log (N)) und eine räumliche Komplexität von O (1) aufweist, und die andere verwendet Linksverschiebung und bitweise Eigenschaften des UND-Operators.
Das obige ist der detaillierte Inhalt vonFibonacci-Binärzahlen (keine aufeinanderfolgenden Einsen im Binärformat) – O(1)-Methode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!