Space efficient iterative method to Fibonacci number | Java code to find nth fibonacci ; get second MSB ; consectutively set all the bits ; returns the second MSB ; Multiply function ; Function to calculate F [ ] [ ] raise to the power n ; Base case ; take 2D array to store number 's ; run loop till MSB > 0 ; To return fibonacci number ; Driver Code ; Given n
class GFG { static int getMSB ( int n ) { n |= n >> 1 ; n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; return ( ( n + 1 ) >> 2 ) ; } static void multiply ( int F [ ] [ ] , int M [ ] [ ] ) { int x = F [ 0 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 0 ] ; int y = F [ 0 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 1 ] ; int z = F [ 1 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 0 ] ; int w = F [ 1 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 1 ] ; F [ 0 ] [ 0 ] = x ; F [ 0 ] [ 1 ] = y ; F [ 1 ] [ 0 ] = z ; F [ 1 ] [ 1 ] = w ; } static void power ( int F [ ] [ ] , int n ) { if ( n == 0 n == 1 ) return ; int [ ] [ ] M = { { 1 , 1 } , { 1 , 0 } } ; for ( int m = getMSB ( n ) ; m > 0 ; m = m >> 1 ) { multiply ( F , F ) ; if ( ( n & m ) > 0 ) { multiply ( F , M ) ; } } } static int fib ( int n ) { int [ ] [ ] F = { { 1 , 1 } , { 1 , 0 } } ; if ( n == 0 ) return 0 ; power ( F , n - 1 ) ; return F [ 0 ] [ 0 ] ; } public static void main ( String [ ] args ) { int n = 6 ; System . out . println ( fib ( n ) ) ; } }