Fast Exponention using Bit Manipulation | Function to return a ^ n ; Stores final answer ; Check if current LSB is set ; Right shift ; Driver code
def powerOptimised ( a , n ) : NEW_LINE INDENT ans = 1 NEW_LINE while ( n > 0 ) : NEW_LINE INDENT last_bit = ( n & 1 ) NEW_LINE if ( last_bit ) : NEW_LINE INDENT ans = ans * a NEW_LINE DEDENT a = a * a NEW_LINE n = n >> 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = 3 NEW_LINE n = 5 NEW_LINE print ( powerOptimised ( a , n ) ) NEW_LINE DEDENT