Fibonacci binary numbers (no consecutive ones in binary) - O(1) method

Fibbinary Numbers are numbers that do not have consecutive 1’s in their binary representation. However, they can have consecutive zeros in their binary representation. Binary representation is a representation that displays numbers using base 2, with only two digits 1 and 0. Here we will be given a number and need to determine if the given number is a fibbinary number.

Input 1: Given number: 10
Output: Yes

Explanation - The binary representation of the given number 10 is 1010, which shows that there are no consecutive ones in the binary form.

Input 2: Given number: 12
Output: No

Explanation − The binary representation of the given number is 1100, which indicates that there are two consecutive 1’s in the binary form.

The Chinese translation of

Naive Approach

is:

Naive Approach

In this method we will use division method to find each bit and store the previous bit by dividing by 2 to get the required information. We will use a while loop until the current number becomes zero.

We will create a variable to store the previously found bit and initialize it to zero. If both the current bit and the previous bit are 1, false is returned, otherwise we repeat until the loop is completed.

After completing the loop, we will return true because no consecutive 1 was found. Let’s take a look at the code −

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;
}

Output

The given number 10 is a Fibbinary Number

Time and space complexity

The time complexity of the above code is O(log(N)) because we divide the current number by 2 until it becomes zero.

The space complexity of the above code is O(1) because we are not using any extra space here.

Efficient method

In the previous method, we checked each bit one by one, but there is another way to solve this problem, and that is the movement of bits. As we know that in Fibbinary numbers, two consecutive bits will not be 1 at the same time, which means that if we shift all the bits to the left by one bit, the bits of the previous number and the current number will be at each position It will never be the same.

For example,

If we take the given number as 10, then its binary form will be 01010, by shifting the bit by 1 bit, we will get the number 10100, we can see that both the numbers do not have 1 bit in the same position .

This is a property of Fibonacci binary numbers, for the number n and the left shift n, they do not have the same bits, making their bitwise AND operator zero.

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;
}

Output

The given number 12 is not a Fibbnary Number

Time and space complexity

The time complexity of the above code is O(1) because all operations are done at the bit level and there are only two operations.

The space complexity of the above code is O(1) because we are not using any extra space here.

in conclusion

In this tutorial, we have seen that a Fibbinary number is a number that does not have consecutive 1's in its binary representation. However, they can have consecutive zeros in their binary representation. We have implemented two methods here, one is using the divide by 2 method, which has a time complexity of O(log(N)) and a space complexity of O(1), and the other is using left shift and bitwise The properties of the AND operator.

The above is the detailed content of Fibonacci binary numbers (no consecutive ones in binary) - O(1) method. For more information, please follow other related articles on the PHP Chinese website!