2의 제곱수를 확인하는 알고리즘(Find the number is power of two)

숫자에 대해 2의 승수(2의 제곱수)인지 확인하는 문제는 면접 시장에서 전설적으로 알려지는 유명한 문제 중 하나이다.

문제 해결에 있어서 초보자이거나, 개발 경험이 부족할 경우 의외로 코드로 옮기는데 힘들어 하는 경우도 많고,

단순한 문제임에도 불구하고 Geek 한 발상이 깃든 최적화된 코드를 유추해낼 수도 있기 때문이다.

숫자가 작을 때에는 직관적으로 숫자가 2의 제곱수인지 판단하기가 쉽지만 숫자가 커지면 쉽지 않다.

다음 수가 2의 제곱수인지 확인해보자

2097152

가장 먼저 짚어내야할 문제의 핵심은 2의 제곱수라면 2의 제곱수가 아닌 다른 수로 이루어져있지 말아야 한다.

그렇다면, 이 성질을 이용해서 숫자를 분해해보면 간단하다. 다음 알고리즘을 생각해볼 수 있다.

bool isMultipleOfTwo(int val) {

//Time Complexity : O(logN)

bool check = true;

while(val > 1) {

int rem = val % 2;

if(val % 2) {

check = false;

break;

}

val /= 2;

}

return check;

}

위의 알고리즘은 입력받은 숫자를 1이 될때까지 2로 나누어본다. 물론 중간에 2로 나누어떨어지지 않으면 숫자는 2의 제곱수가 아니기 때문에 Loop 를 벗어난다.

문제를 푸는데 익숙치 않은 일부 개발자를 제외하고는 거의 대부분의 개발자가 생각하는 알고리즘이며, 시간 복잡도는 O(logN) 이다.

그렇다면 좀 더 특별하게 풀 수 있는 방법은 있을까

컴퓨터가 숫자를 다루는 방식이 2진수라는 걸 고려하면 손쉽게 풀 수 있다. 즉, 2진수에서 2의 제곱수는 수를 구성하는 Bit가 단 한개의 1로 구성되어 있어야 한다. 따라서 다음과 같은 코드가 Optimal 이다.

bool isMultipleOfTwoOptimal(int val) {

//Time Complexity : O(1)

return val && (!(val&(val-1)));

}

이제 처음에 제시한 수의 결과를 확인해보자.

#include <iostream>

using namespace std;

bool isMultipleOfTwo(int val) {

//Time Complexity : O(logN)

bool check = true;

while(val > 1) {

int rem = val % 2;

if(val % 2) {

check = false;

break;

}

val /= 2;

}

return check;

}

bool isMultipleOfTwoOptimal(int val) {

//Time Complexity : O(1)

return val && (!(val&(val-1)));

}

void printCheck(bool check) {

if(check) {

cout<<"Multiples of Two"<<endl;

} else {

cout<<"Not multiples of Two"<<endl;

}

}

int main()

{

int val = 2097152;

bool check = isMultipleOfTwo(val);

bool checkOptimal = isMultipleOfTwoOptimal(val);

printCheck(check);

printCheck(checkOptimal);

return 0;

}

결과는 두 방식 모두 2의 제곱수임을 출력한다.

Multiples of Two

Multiples of Two

위의 문제는 Find whether the number is power of two 라는 실리콘밸리에서 흔히 알려진 면접문제이다. 고로 면접장에서 실제 볼 확률은 드물지만, 문제를 접근하는 참신한 방법은 배울 점이 많다.