What are Fibbinary numbers?

Overview

A Fibbinary number is an integer that has no consecutive set bits (ones) in its binary representation.

For example, the binary representation of 3 is 011. It’s not a Fibbinary number since the binary representation contains adjacent set bits.

In the following part of this shot, we’ll learn to check whether a given number n is a Fibbinary number or not.

Checking if a number is a Fibbinary number

To check if a number is Fibbinary, we’ll use shift operators and the bitwise AND operation.

The steps of the solution are as follows:

  1. Shift the number left or right by 1. For the left shift operator, use n & (n << 1). For the right shift operator, use n & (n >> 1).
  2. Perform a bitwise AND operation on the number and the result from step 1. If the result from step 2 is greater than zero, then it means that there are adjacent set bits and the number is not a Fibbinary number. Otherwise, we can conclude that there are no adjacent set bits and the number is a Fibbinary number.

For example, let’s consider n=6. First, we use the left shift operator.

  • n = 6 (0110)
  • (n << 1) = 12 (1100)
  • n & (n << 1) = 4 (0100)

Since n & (n << 1) is greater than zero, we know that there are adjacent set bits in the given number. Hence, we can conclude that 6 is not a Fibbinary number.

Now, let’s consider n=4. Again, we first use the left shift operator.

  • n = 4 (0100)
  • (n << 1) = 8 (1000)
  • n & (n << 1) = 0 (0000)

Since n & (n << 1) is zero, we know that there are no adjacent set bits in the given number. Hence, we can conclude that 4 is a Fibbinary number.

Code

public class Main {
    public static void main(String[] args) {
        int n = 1;
        boolean res = (n & (n << 1)) == 0;
        if(res)  System.out.println(n + " is a Fibbinary number");
        else System.out.println(n + " is not a Fibbinary number");
    }
}
Example of finding a Fibbinary number in Java

Explanation

  • Line 4: We define an integer n.
  • Line 5: We check whether there are adjacent set bits in n using the expression n & (n << 1) and check whether the result is zero or not.
  • Lines 6–7: Based on the result from line 5, we print either that n is a Fibbinary number or that it isn’t a Fibbinary number.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)