알고리즘 문제에서 종종 주어진 수가 2의 제곱수($2^{n}$)인지 확인할 필요가 있다.
아래는 이를 위해 구현된 몇가지 예시들이다.

while 문 사용

가장 쉽게 생각할 수 있는 방법 중 하나로 주어진 숫자를 2로 나누어 1이 될때까지 while문을 실행하는 방법이다.
중간에 2와 나머지 연산을 통해 0이 아니라면 while문을 빠져나오게 만든다.

Implement

#include <iostream>

bool isPowerofTwo(int n)
{
	if (n == 0) 
    	return false;
    
   	while (n != 1)
    {
    	if (n % 2 != 0) 
        	return false;
        n = n / 2;
    }
    
    return true;
}

int main()
{
    isPowerOfTwo(31) ? cout << "Yes" << endl : cout << "No" << endl; // No
    isPowerOfTwo(64) ? cout << "Yes" << endl : cout << "No" << endl; // Yes
 
    return 0;
}

시간 복잡도(Time Complexity): $O(logN)$

---

재귀(recursion) 사용

첫 번째 방법인 while문과 비슷하지만 대신 재귀(recursion)를 사용한 방법이다.

Implement

#include <iostream>

bool isPowerofTwo(int n)
{
	if (n == 1)
    	return true;
	else if (n % 2 != 0 || n == 0)
    	return false;

	return isPowerofTwo(n / 2);
}

int main()
{
    isPowerOfTwo(12) ? cout << "Yes" << endl : cout << "No" << endl; // No
    isPowerOfTwo(64) ? cout << "Yes" << endl : cout << "No" << endl; // Yes
 
    return 0;
}

시간 복잡도(Time Complexity): $O(logN)$

---

$log_2$ 사용

주어진 숫자를 $log_2$를 취해 각각 올림, 내림을 하여 비교하는 것이다.
2의 제곱수라면 $log_2$를 취해 각각 올림, 내림을 하여도 같은 값을 가지고 아니라면 1의 차이를 가지기 때문에 2의 제곱수인지 확인할 수 있다.

Implement

#include <cmath>
#include <iostream>

bool isPowerofTwo(int n)
{
	if (n == 0)
    	return false;
    
    return (ceil(log2(n)) == floor(log2(n)));
}

int main()
{
    isPowerOfTwo(31) ? cout << "Yes" << endl : cout << "No" << endl; // No
    isPowerOfTwo(64) ? cout << "Yes" << endl : cout << "No" << endl; // Yes
 
    return 0;
}

시간 복잡도(Time Complexity): $O(1)$

---

비트 연산자 AND(&) 사용

비트 연산을 사용하여 2의 제곱수인지 확인하는 방법 중 하나로 비트 연산자 AND(&)를 사용한다.
원리는 아래와 같다.

2의 제곱수인 $4_{10}(100_2)$와 $16_{10}(10000_2)$가 있다고 할때, 두 수에 각각 1씩 감소시키면 다음과 같다.

$3_{10}$ → $011_2$
$15_{10}$ → $01111_2$

따라서 만약 2의 제곱수인 숫자와 해당 숫자를 1 감소 시킨 숫자를 비트 연산자 AND(&)를 하게 되면 0이 나오게 되고 쉽게 2의 제곱수인지 아닌지 확인할 수 있다.

$4_{10}$ & $3_{10}$ → $100_2$ & $011_2$ → $0$
$16_{10}$ & $15_{10}$ → $10000_2$ & $01111_2$ → $0$

그렇다면 2의 제곱수가 아니라면 어떻게 될까?
2의 제곱수가 아닌 $3_{10}(011_2)$와 $15_{10}(1111_2)$를 각각 1 감소 시켜 AND(&) 연산을 하게 되면 다음과 같다.

$3_{10}$ & $2_{10}$ → $11_2$ & $10_2$ → $10_2 == 2_{10}$
$15_{10}$ & $14_{10}$ → $1111_2$ & $1110_2$ → $1110_2 == 14_{10}$

즉, 0이 아닌 수가 나오고 이를 이용해 2의 제곱수가 아님을 확인할 수 있다.

Implement

#include <iostream>

bool isPowerofTwo(int n)
{
    return n && (!(n & (n - 1)));
}

int main()
{
    isPowerOfTwo(31) ? cout << "Yes" << endl : cout << "No" << endl; // No
    isPowerOfTwo(64) ? cout << "Yes" << endl : cout << "No" << endl; // Yes
 
    return 0;
}

시간 복잡도(Time Complexity): $O(1)$

---

비트 연산자 AND(&), NOT(~) 사용

비트 연산자 AND(&)와 NOT(~)를 사용하여 2의 제곱수인지 확인하는 방법으로 원리는 아래와 같다.

2의 제곱수인 $4_{10}(100_2)$와 $16_{10}(10000_2)$가 있다고 할때, 두 수에 각각 1씩 감소시키면 다음과 같다.

$3_{10}$ → $011_2$
$15_{10}$ → $01111_2$

2의 제곱수인 숫자에 1 감소 시킨 숫자를 비트 연산자 NOT(&)를 하고 주어닞 2의 제곱수와 AND(&) 연산을 하게 되면 주어진 2의 제곱수가 나와 2의 제곱수인지 확인 할 수 있다.

$4_{10}$ & (~$3_{10}$) → $100_2$ & (~$011_2$) → $100_2$ & $100_2$ → $100_2 == 4_{10}$
$16_{10}$ & (~$15_{10}$) → $10000_2$ & (~$01111_2$) → $10000_2$ & $10000_2$ → $10000_2 == 16_{10}$

그렇다면 2의 제곱수가 아니라면 어떻게 될까?
2의 제곱수가 아닌 $3_{10}(011_2)$와 $15_{10}(1111_2)$를 같은 방법을 적용하면 아래와 같다.

$3_{10}$ & (~$2_{10}$) → $11_2$ & (~$10_2$) → $11_2$ & $01_2$ → $01_2 == 1_{10}$
$15_{10}$ & (~$14_{10}$) → $1111_2$ & (~$1110_2$) → $1111_2$ & $0001_2$ → $0001_2 == 1_{10}$

주어진 수가 결과값으로 나오지 않기 때문에 2의 제곱수가 아님을 확인할 수 있다.

Implement

#include <iostream>

bool isPowerofTwo(int n)
{
	if (n == 0)
    	return false;
    if ((n & (~(n - 1))) == n)
    	return true;
        
    return false;
}

int main()
{
    isPowerOfTwo(30) ? cout << "Yes" << endl : cout << "No" << endl; // No
    isPowerOfTwo(128) ? cout << "Yes" << endl : cout << "No" << endl; // Yes
 
    return 0;
}

시간 복잡도(Time Complexity): $O(1)$

---

참고 자료

• https://www.geeksforgeeks.org/program-to-find-whether-a-given-number-is-power-of-2/