Fast Exponentiation

Problem

Compute base raised to a non-negative integer exponent using binary exponentiation in O(log exp) multiplications.

Square the base while halving the exponent, multiplying the result whenever the current exponent bit is set. Return the exact integer result; base may be zero or negative.

Hint

Peel off one bit of the exponent at a time while squaring the base.

Test cases

case 1

in: [2,10]

expected: 1024

case 2

in: [5,0]

expected: 1

case 3

in: [0,0]

expected: 1

case 4

in: [-3,3]

expected: -27

case 5

in: [7,1]

expected: 7

Starter codePython

def power(base, exp):
    # Your code here
    pass

5 test cases · run your code against them in the editor