Open WonYong-Jang opened 6 years ago
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) ; } }
==> 21 을 비트로 표현 해보면 10101
ex) 16 -> 2^4 ( true ) ex) 218 -> false
2의 제곱인 숫자를 비트연산자로 표현해 보면 1 10 100 1000 ... 으로 맨 좌측 숫자가 1이고 나머지는 0이다.
즉, 입력받은 숫자가 2의 제곱인지 확인하려면 위의 형태인지를 순차적으로 확인하는 방법이 있지만 int는 32bit만 표현이 가능하고 더 큰 경우는 시간 초과!
n & (n-1)
ex ) https://leetcode.com/problems/power-of-two/
일반적인 방법
분할정복 알고리즘
지수를 2의 거듭제곱 형태로 표현
==> 21 을 비트로 표현 해보면 10101