left-to-right-binary-exponentiation.cpp

#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;

vector<bool> getbase2rep (uint64_t ninput)
{
    vector<bool> result;
    do {
        if (ninput % 2 == 0) {
            result.insert (result.begin (), false);
        } else {
            result.insert (result.begin (), true);
        }
    } while (ninput /= 2);

    return result;
}

uint64_t left2right_powers (uint64_t ninput, uint64_t power)
{
    vector<bool> bpower = getbase2rep (power);
    uint64_t pow = 1;

    for (auto p : bpower) {
        if (p == 0) {
            pow *= pow;
        } else {
            pow *= pow * ninput;
        }
    }

    return pow;
}


int main (int argc, char* argv[])
{
    uint64_t ninput, npower, ans;

    ninput = strtol (argv[1], NULL, 10);
    npower = strtol (argv[2], NULL, 10);

    ans = left2right_powers (ninput, npower);
    printf ("%lu\n", ans);

    return 0;
}