2의 n제곱 수인지 판별하기

 

 

---

1. 개 요

2의 n제곱 수를 2진수로 나타낸다면

 

 

2의 1제곱 2 -> 10

 

2의 4제곱 16 -> 10000

 

2의 6제곱 64 -> 1000000

 

2의 0제곱 1 -> 1

 

와 같이 1로 시작하며 오른쪽의 0이 채워지는 형태이다.

 

 

그렇다면 이제 각 수에서 1을 뺀 수를 2진수로 나타내보면

 

(2의 1제곱-1) 1 -> 1

 

(2의 4제곱-1) 15 -> 1111

 

(2의 6제곱-1) 63 -> 111111

 

(2의 0제곱-1) 0 -> 0

 

그러면 여기서 0제곱을 제외하고는 1로 2진수가 1로 이루어진 것을 확인 할 수 있다.

 

 

 

그렇다면 이와 같은 사실을 이용하여서 임의의 수 n이 2의 제곱수인지 판별할 수 있다.

 

 

& 비트 연산자는 둘 다 1이여야만 1이 된다. 

 

임의의 수 n과 n-1를 비트 연산자 &를 사용하여 연산하면 n이 2의 제곱 수인 경우 그 결과 0이 도출된다. 

 

 

 

 

 

---

2. 코 드

 환경 : Visual Studio 2019

 

#include <iostream>
using namespace std;

bool twoN(int num) {
	return (num & (num - 1)) == 0;
}

int main() {
	int n[6] = { 1, 17, 64, 1025, 2048, 2047 };
	
	for (int i = 0; i < 6; i++) {
		if (twoN(n[i])) {
			cout << n[i] << "는 2의 n제곱 수이다.\n";
		}
		else {
			cout << n[i] << "는 2의 n제곱 수가 아니다.\n";
		}
	}

	return 0;
}

 

 

결과

 

 

 

 

이처럼 간편하게 임의의 수 n이 2의 제곱 수인지 판별할 수 있다.