A^n (n은 자연수) 을 구하는 문제를 n번 곱해 푼다면 O(n)이 걸린다.
하지만 n을 2진수로 변환하면 특정한 규칙을 찾을 수 있다.
이처럼 변환된 지수의 비트하나씩 & 1 연산해서 값이 1이나올때만
그 수를 곱해주면 곱할수 n을 2의제곱씩 묶어서 계산이 가능하므로 O(log n)로 풀 수 있다.
실제로 구현하면 아래와 같다.
홀수가나오는것은 해당 비트가 1이었던것을 의미 하므로 이때의값을 출력값 res에 곱해준다. (res = 1에서부터 시작한다.)
또한 2진수의 각 비트하나씩 탐색할때마다 A를 제곱 해주면
A^1, A^2, A^4... 처럼 간단하게 2의 제곱수만큼 대응시킬 수 있다.
마지막으로 n에해당하는 B를 오른쪽쉬프트해서 B /= 2 하며 반복한다.
I will be a socially developer