How to find the Nth XOR Fibonacci number in C++

By Tanmaay Kankaria

In this article, given three numbers a, b and n, where a and b are the first two terms of the XOR Fibonacci series, we have to find the n^th term. The Nth term of the XOR Fibonacci series is defined as F(N) = F(N – 1) ^ F(N – 2) where ^ is the operator for bitwise XOR. The time complexity of our code is O(1).

Nth XOR Fibonacci number in C++

Let’s take the help of an example.

Input: a = 1, b = 2, N = 5
Output: 3

Working:

F(0) = 1
F(1) = 2
F(2) = 1 ^ 2 = 3
F(3) = 2 ^ 3 = 1
F(4) = 1 ^ 3 = 2
F(5) = 1 ^ 2 = 3

Code Implementation:

#include <bits/stdc++.h> 
using namespace std; 
 
int nXorFib(int n, int a, int b) 
{ 
  if (n == 0) 
    return a; 
  if (n == 1) 
    return b; 
  if (n == 2) 
    return (a ^ b);
  return nXorFib(n % 3, a, b); 
} 
 
int main() 
{ 
  int a,b,n;
        cout<<"Enter the value of a \n";
        cin>>a;
        cout<<"Enter the value of b \n";
        cin>>b;
        cout<<"Enter the value of n \n";
        cin>>n;
  cout<<nXorFib(n, a, b); 
  return 0; 
} 

Working of Code:

Since, a ^ a = 0 and it is given that

F(0) = a , F(1) = b

F(2) = F(0) ^ F(1) = a ^ b
F(3) = F(1) ^ F(2) = b ^ (a ^ b) = a
F(4) = a ^ b ^ a = b
F(5) = a ^ b
F(6) = a
F(7) = b
F(8) = a ^ b and so on.

We can notice that the result repeats itself every 3 numbers. Thus the answer is F(N % 3) where F(0) = a, F(1) = b and F(2) = a ^ b.

I hope, you have understood how our program works to find the Nth XOR Fibonacci number in C++ language.

You may also learn,

• Generate Fibonacci Triangle in C++