Fast (Binary) Exponentiation

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {

}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

        // If the lowest bit of n is set, the current power of x belongs in the result.
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

    for n > 0 {
        // If the lowest bit of n is set, the current power of x belongs in the result.
        if n&1 == 1 {
            result *= x
        }
    }
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

    for n > 0 {
        // If the lowest bit of n is set, the current power of x belongs in the result.
        if n&1 == 1 {
            result *= x
        }

        // Move to the next bit: square the base and shift n right by one.
    }
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

    for n > 0 {
        // If the lowest bit of n is set, the current power of x belongs in the result.
        if n&1 == 1 {
            result *= x
        }

        // Move to the next bit: square the base and shift n right by one.
        x *= x
        n >>= 1
    }
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

    for n > 0 {
        // If the lowest bit of n is set, the current power of x belongs in the result.
        if n&1 == 1 {
            result *= x
        }

        // Move to the next bit: square the base and shift n right by one.
        x *= x
        n >>= 1
    }

    // For modular exponentiation, take % mod after each *= (result and x).
}

// power returns x^n for n >= 0 in O(log n) multiplications.
func power(x, n int) int {
    // x^n = product of x^(2^b) for each set bit b of n. Start the product at 1.
    result := 1

    for n > 0 {
        // If the lowest bit of n is set, the current power of x belongs in the result.
        if n&1 == 1 {
            result *= x
        }

        // Move to the next bit: square the base and shift n right by one.
        x *= x
        n >>= 1
    }

    // For modular exponentiation, take % mod after each *= (result and x).
    return result
}