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:
- Shift the number left or right by 1. For the left shift operator, use
n & (n << 1). For the right shift operator, usen & (n >> 1). - Perform a bitwise
ANDoperation 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");}}
Explanation
- Line 4: We define an integer
n. - Line 5: We check whether there are adjacent set bits in
nusing the expressionn & (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
nis a Fibbinary number or that it isn’t a Fibbinary number.
