비트 벡터를 이용하던 중에 결과 값 중에 1로 세팅된 비트가 단 한개인지 확인할 필요가 있었는데 기발한 풀이법이 있어서 기록하여 나중에 참고하기 위한 글입니다. 예를 들어
00010000와 같은 값이 있으면 참을 반환하고00010100은 거짓을 반환해야 합니다.
비트 벡터란 (Bit Vector)
풀이 법
풀이 법으로 시프트 연산을 이용하는 방법, 1로 세팅된 비트가 한 개 이면 정수 값이 2의 승수인 특징을 이용하는 방법 등을 생각해 볼 수 있지만 이 방법을 이용하면 연산 두 번만으로 간단히 해결할 수 있습니다.
이 풀이 법의 핵심 비트 연산에서 뺄셈의 특징을 이용하는 것입니다. 예를 들어 1000에 1을 빼면 0111 이 되고 두 값은 모든 비트에 대해 서로 다른 값을 갖게 됩니다. 각각의 비트가 모두 다른 값을 가지고 있으므로 두 값에 대해 & 연산을 하면 결과 값은 0이 됩니다. 하지만 1인 비트가 2개 이상이라면 높은 자리 수에 1이 남아 있게 돼서 & 연산을 하면 1이 남기 때문에 결과 값은 0보다 큰 값이 됩니다. 이 특징을 이용하여 1의 개수가 1개 이하인지 2개 이상인지를 판단할 수 있습니다. 예를 들어서 자세히 살펴봅시다.
예시
00010000
00010000 - 1 -> 00001111
00010000 & 00001111 -> 00000000
결과 값 = 0 이므로 1의 개수는 1개 이하
00010100
00010100 - 1 -> 000010100
00010100 & 00010011 -> 00010000
결과 값 > 0 이므로 1의 개수는 2개 이상
00000000
00000000 - 1 -> 11111111
00000000 & 11111111 -> 00000000
결과 값 = 0 이므로 1의 개수는 1개 이하
결론
if (x & (x - 1) == 0) {
// x 의 비트 값 중에 1인 개수 1개 이하
}
else {
// x 의 비트 값 중에 1인 개수는 2개 이상
}
참고자료
- 코딩 인터뷰 완전 분석 - 게일 라크만 맥도웰 지음, 이창현 옮김