Binary Exponentiation 

#include "bits/stdc++.h"
#define ma_mod(a,n)        ((a%n)+a)%n

int binExpIter(int a,int b){
    int ans = 1;
    while(b){
        if(b&1) ans = (ans * a) %M;
        a = (a*a) % M;
        b >>= 1;
    }
    return ans;
}

Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate an<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>a</mi><mi>n</mi></msup></math>$a^n$ using only O(log⁡n)<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo data-mjx-texclass="NONE">⁡</mo><mi>n</mi><mo stretchy="false">)</mo></math>$O(\log n)$ multiplications (instead of O(n)<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math>$O(n)$ multiplications required by the naive approach).

It also has important applications in many tasks unrelated to arithmetic, since it can be used with any operations that have the property of associativity: