For powers of two all you have to do is use the shifter, which is very
fast and is probably almost constants for the usual powers of 2.

For ordinary numbers, its probably the O(exp), where exp is the
exponent. For example, base^exp, to calculate that it would probably take exp times to multiply base to get the answer.

The above is not definite, its just a hunch.

It is at worst O(log(exp)). For example:
^2: x*x
^4: x2 = x*x, x^4 = x2 * x2
^8: x2 = x*x, x4 = x2*x2, x^8 = x4 * x4
etc.

In the general case, the multiplication schedule is a bit hairy (and finding the best one is probably NP-hard).

PS: this is assuming that a multiplication itself has a constant complexity, which is definitely wrong.

thanks for the info guys