비트연산자로 2의 제곱수 여부 확인하기!

2의 제곱수를 비트연산자를 이용하면 훨씬 간단하게 알아낼 수 있다.

기존에는 입력값을 2로 계속 나누는 식으로 알아냈는데, 비트연산자를 이용하면 반복문을 사용하지 않고도 풀 수 있다.

 

작년, 논리회로 수업을 들을 때 부호를 바꾸는 비트연산을 한 적이 있다. 방법은 해당 비트를 모두 반대로 뒤집은 다음, 1을 더해주는 식인데 예를 들자면 이렇다.

 

36를 -36로 바꿔보자. (8비트)

1. 일단 36를 비트로 표현한다.

-> 00100100

2. 비트를 모두 뒤집어준다. (0->1, 1->0)

-> 11011011

3. 1을 더해준다.

-> 11011100

 

위와 같이 부호를 바꾸는 연산을 할 수가 있는데, 이 때 공통점은 오른쪽부터 시작해서 가장 처음 만나는 1까지는 그대로이고, 그보다 왼쪽의 비트들만 뒤집힌다는 점이다.

 

0 0 1 0 0 1 0 0 --> 위의 예시로 보자면 00100100에서 가장 오른쪽의 1을 찾고,

|  |  |  |  |  |  |  | 

1 1 0 1 1 1 0 0 --> 그 1보다 오른쪽의 비트들은 그대로 두고, 왼쪽에 있는 비트들만 뒤집으면

위에서 계산했던 결과와 같게 나오는 것을 확인 할 수 있다.

 

이러한 규칙 때문에 부호만 다른 두 수를 서로 AND 연산을 할 경우 가장 오른쪽의 1을 제외하고 전부 0으로 바뀌게 된다.

위의 00100100과 11011100을 AND연산을 한다면 00000100이 나오게 된다.

 

여기서 2의 제곱수들은 항상 1인 비트가 한개밖에 없기 때문에 부호만 다른 수와 AND연산을 하게 되면 다시 자기 자신이 나올 수 밖에 없다.

이러한 특성을 이용해서 코드를 짜본다면

 

#include <iostream>
using namespace std;

int main() {
	int input;
	cin >> input;

	//2의 제곱수는 반대부호와 &연산을 해도 자기 자신과 같다.
	if (input == (-input & input)) cout << "2의 제곱수입니다.";
	else cout << "2의 제곱수가 아닙니다.";

	return 0;
}

 

위와 같이 반복문을 사용하지 않고도 2의 제곱수를 알아낼 수 있다.