문제 개요
양의 정수가 하나 주어졌을 때, 이 수가 교대 비트(alternating bits)를 가지고 있는지 확인해야 합니다. 교대 비트란 인접한 두 비트가 항상 서로 다른 값을 갖는 경우를 의미합니다.
예를 들어 입력값이 10이라면 출력은 True입니다. 10의 이진 표현은 1010으로, 모든 인접 비트가 서로 다른 값을 가지기 때문입니다.
해결 접근 방법
이 문제는 숫자를 오른쪽으로 시프트하면서 최하위 비트를 하나씩 검사하는 방식으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- p := n AND 1 (n의 최하위 비트를 p에 저장)
- n < 2이면 true 반환 (비교할 인접 비트가 없으므로)
- n := n / 2 (오른쪽 시프트)
- n이 0이 아닌 동안 반복:
- c := n AND 1 (현재 최하위 비트 저장)
- c XOR p의 결과가 0이면 false 반환 (인접한 두 비트가 같다는 의미)
- p := c
- n := n / 2
- 반복이 끝나면 true 반환
핵심 아이디어는 XOR 연산에 있습니다. 두 비트가 서로 다르면 XOR 결과는 1이 되고, 같으면 0이 됩니다. 따라서 c ^ p == 0인 순간이 있다면 인접 비트가 동일하다는 뜻이므로 교대 비트가 아니라고 판단할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool hasAlternatingBits(int n) {
bool p=n&1;
bool c;
if(n<2)
return true;
n>>=1;
while(n){
c=n&1;
if(c^p==0)
return false;
p=c;
n>>=1;
}
return true;
}
};
main(){
Solution ob;
cout << (ob.hasAlternatingBits(10));
}입력
10
출력
1
출력값 1은 bool 타입의 true가 정수로 변환된 결과로, 입력 10이 교대 비트를 가진 수임을 의미합니다.