[알고리즘] 빠른 거듭제곱 알고리즘 (bit set을 이용한 빠른 거듭제곱)

상아탑 6주차 중

거듭제곱을 빠르게 계산하는 알고리즘 (ex. 3^2500000000....)

 

우선 지수를 이진법으로 표현하고, 이것을 exp로 설정

base = 밑

#include <iostream>

int power(base, exp) {
	int ret = 1; // 결과값을 1로 우선 설정
	while(exp){ //exp가 존재하는 동안 = 자릿수를 모두 이동하는 동안
		if(exp & 1 == 1) ret *= base; //1번째 자리가 1일 경우 ret*=base
		exp >>= 1; //오른쪽 옆으로 한 칸씩 이동 
		base *= base; //base를 제곱해줌. 이진법에 따라 자릿수 이동할 때마다 실제 숫자는 제곱
	}
	return ret; //ret값을 반환
}

 

위와 같은 코드를 이용해 bit set을 응용한 빠른 거듭제곱 알고리즘을 설계할 수 있다.