거듭제곱 알고리즘 [백준 1629번 ]

[WonYong-Jang]

일반적인 방법

분할정복 알고리즘

• O(logN)

public static long pow(long a, long b)
{
	long k =0;
	if ( b == 0 ) return 1;
		
	else if(b % 2 == 0) { // 거듭제곱이 짝수일 때 
		k = pow(a, b/2);
		return (k * k) ;
	}
	else {                         // 거듭제곱이 홀수일 때
		k = pow(a, (b-1)/2);
		return (a * k *k) ;
	}
}

지수를 2의 거듭제곱 형태로 표현

• O(log지수)
  7^21 = ( 7^16 ) * ( 7^4 ) * ( 7 )

==> 21 을 비트로 표현 해보면 10101

[WonYong-Jang]

2의 제곱수인지 확인 !

ex) 16 -> 2^4 ( true )
ex) 218 -> false

2의 제곱인 숫자를 비트연산자로 표현해 보면
1
10
100
1000 ...
으로 맨 좌측 숫자가 1이고 나머지는 0이다.

즉, 입력받은 숫자가 2의 제곱인지 확인하려면 위의 형태인지를 순차적으로 확인하는 방법이 있지만
int는 32bit만 표현이 가능하고 더 큰 경우는 시간 초과!

n & (n-1)

• 위의 식이 0인지를 확인하면 된다!
• n은 좌측이 1 나머지가 0이며, n-1은 좌측 0이며 나머지가 모두 1인 상태이다!!
• 두 수를 and 연산자로 0이되는 지를 확인한다.

ex ) https://leetcode.com/problems/power-of-two/