백준 1094 막대기 (비트 개수 세기)

출처: https://www.acmicpc.net/problem/1094

분류: 비트마스킹

---

접근방식

주어진 문제의 조건을 맹목적으로 따라서 풀 수도 있지만,
조건을 해보면 결국은 주어진 x를 몇 개의 2의 배수를 사용해 만들 수 있느냐 하는 문제입니다.

다시 생각해보면 "x를 이진수로 만들었을 때 1이 몇 개냐" 라는 말과 같은 말이라는 걸 알 수 있습니다 :)

 

따라서 이진수에서 1이 몇 개인지 세는 방법을 알아보겠습니다.

 

2로 나누기

우선 비트 연산을 하지 않는다면 주어진 수를 x로 나눠가면서 셀 수가 있겠네요.
중학생(?)때 배우는 10진수를 2진수로 바꿀 때 나눠가면서 나머지를 세는 바로 그 방식입니다.

while x > 0 {
    bitCount += x % 2
    x /= 2
}

 

>> 1

2로 나누는 걸 비트연산으로 하려면 오른쪽으로 쉬프트 1 해주면 되겠네요
그 전에 마지막 비트가 켜져있는지 1과 &연산을 통해 확인합니다.

while x > 0 {
    bitCount += x & 1
    x >>= 1
}

 

x & (x-1 )

어떤 수와 그보다 1작은 수를 &연산 하면 마지막 비트를 꺼줄 수 있습니다.

이건 직접 해보면 금방 이해가 가실텐데요,

예를 들어,

4는 이진수로 100 이고 3은 이진수로 011이 됩니다.
4의 마지막 비트를 0으로 바꿔주고 싶네요, 1은 하나뿐이니 연산 결과가 0이 되면 되겠죠?
4와 3을 &연산하면 0이 됩니다. 

10는 이진수로 1010이고 9는 1001 입니다.
10의 마지막 비트를 꺼주면 2자리 비트가 꺼지고 결과는 1000이 되어야겠네요.
10과 9를 &연산하면 결과는 1000이 됩니다 :)

while x > 0 {
    x &= (x-1)
    bitCount += 1
}

 

해결방법

var x = Int(readLine()!)!
var bitCount = 0
while x > 0 {
    // 맨 마지막 비트가 꺼짐
    x &= (x-1)
    bitCount += 1
}
print(bitCount)

 

배운점

비트 연산으로 참 많은 걸 할 수 있다.

신비로운 세계 :(