Clinic #31: Pow(x, n)

Pattern: Fast exponentiation · LC 50

Shows a number as a row of switches, and the moves a computer makes on that row in one step. This clinic uses two of them, “is the lowest switch on?” and “slide the row one place right”, to raise a number to a two-billionth power in 31 steps.

Before you start. Bit Manipulation (thinking in bits) showed that every whole number is stored as a row of 1s and 0s, and that sliding the row one place to the right halves the number, dropping any remainder. Complexity & Big-O gave the other idea you need: an answer whose cost goes up by one step each time the input doubles is called O(log n).