Iterative function for pow(x, y)

Given two integers x and y, compute x^y efficiently. The approach should run in O(log y) time complexity and use O(1) auxiliary space.

Examples: 

Input: x = 3, y = 19
Output: 1162261467
Explanation: 3¹⁹ = 1162261467

Input: x = 2, y = 5
Output: 32
Explanation: 2⁵ = 32

Binary Exponentiation - O(log y) Time and O(1) Space

Instead of multiplying x repeatedly y times, we use the binary representation of y to make the computation faster. Every number can be written as the sum of powers of 2, so we only need to consider those powers where the binary bit is 1.

We traverse through all the bits of y from LSB to MSB.

• If the current bit is 1, we multiply our answer with x.
• If the current bit is 0, we ignore it.
• At every step, we square x (to get the next power) and divide y by 2 to move to the next bit.

using namespace std;

int power(int x, int y) {
    int res = 1;

    while (y > 0) {

        // if y is odd, last bit is 1 so include this power
        if (y & 1) {
            res = res * x;
        }

        // square the base
        x = x * x;

        // move to next bit
        y = y >> 1;
    }

    return res;
}

int main() {
    int x = 3;
    int y = 19;
    cout << power(x, y);
    return 0;
}

class GFG {

    static int power(int x, int y) {
        int res = 1;

        while (y > 0) {

            // if y is odd, last bit is 1 so include this power
            if ((y & 1) == 1) {
                res = res * x;
            }

            // square the base
            x = x * x;

            // move to next bit
            y = y >> 1;
        }

        return res;
    }

    public static void main(String[] args) {
        int x = 3;
        int y = 19;
        System.out.println(power(x, y));
    }
}

def power(x, y):
    res = 1

    while y > 0:

        # if y is odd, last bit is 1 so include this power
        if (y & 1) == 1:
            res = res * x

        # square the base
        x = x * x

        # move to next bit
        y = y >> 1

    return res


if __name__ == "__main__":
    x = 3
    y = 19
    print(power(x, y))

using System;

class GFG {

    static int power(int x, int y) {
        int res = 1;

        while (y > 0) {

            // if y is odd, last bit is 1 so include this power
            if ((y & 1) == 1) {
                res = res * x;
            }

            // square the base
            x = x * x;

            // move to next bit
            y = y >> 1;
        }

        return res;
    }

    static void Main() {
        int x = 3;
        int y = 19;
        Console.WriteLine(power(x, y));
    }
}

function power(x, y) {
    let res = 1;

    while (y > 0) {

        // if y is odd, last bit is 1 so include this power
        if (y & 1) {
            res = res * x;
        }

        // square the base
        x = x * x;

        // move to next bit
        y = y >> 1;
    }

    return res;
}

// driver code
let x = 3;
let y = 19;
console.log(power(x, y));

1162261467