[bit masking] 1094번, 막대기

오늘 소개할 문제는 백준 사이트에 있는 1094번 문제 <막대기>이다. 

문제는 아래 링크를 통해서 확인할 수 있다.

 

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

1094번: 막대기

 

이 문제를 푸는 방법은 다양하다. 

bit masking을 사용하여 1줄 coding을 해보자.

 

1. 문제 파악

막대기의 길이는 64cm로 고정되어 있다. 

막대기를 부러뜨려서 만들 수 있는 길이는 다음과 같다.

64cm, 32cm, 16cm, 8cm, 4cm, 2cm, 1cm

문제에서 나올 xcm의 최대값은 64cm이고, 최소값은 1cm이 된다.

위 숫자를 보면 2의 거듭제곱수라는 것을 알 수 있다. 

bit masking 이해

 

여기서 잠깐 컴퓨터가 10진수를 저장하는 방법을 알아야 한다.

알고 있듯이 컴퓨터는 사람이 사용하는 10진수로 정보를 저장하지 않고, 2진수로 정보를 저장한다. 

위 그림을 기억하면서 몇가지 예를 들어 보자. 

ex)

36 = 32 + 4 = 100100

17 = 16 + 1 = 10001

30 = 16 + 8 + 4 + 2 = 11110

 

이렇게 2의 거듭제곱의 합으로 모든 숫자는 표현할 수 있다. 

지금 예시를 통해서 아! 하고 느낌이 왔다면, 맞다 바로 그거다.

bit로 표현된 값에서 1의 개수가 바로 답이다.

 

문제에서 주어지는 모든 수는 8bit 내에서 1과 0으로 표현이 된다. 

각각의 bit를 다 더하면, 그게 바로 답이 된다. 

 

그럼 bit를 어떻게 다 더하냐고 물어볼 수 있는데, 

이 때 사용하는 것이 bit 연산자이다. 

bit를 가지고 노는데 필요한 연산자들이다. 

bit연산자니까 연산 우선순위가 높겠지라고 생각할 수 있는데 천만에 말씀이다. 

기본 사칙연산은 우리가 기억하기 쉽지만, 그 외 연산자들의 우선순위를 다 외울 수 없다. 

이 때 필요한 게 바로!! 괄호이다.

괄호를 치는 순간 컴퓨터에게 내가 괄호친 이 연산을 젤 먼저 해줘 라고 알려주는 것이다. 

귀찮다고 생각하지 말고, 아리송송할 때는 괄호를 치자. 

 

">>" 연산자는 왼쪽으로 몇칸 이동했는지를 나타낸다. 

64cm이면, 1000000 이다. 

여기서 1을 왼쪽으로 이동시킨다고 생각하면 6칸 옮기면 된다.

64 >>6  = 0000001 이다. 

즉 각 자리에 위치한 1을 오른쪽 끝, LSB(least significant bit, 가장 오른쪽 비트를 의미할 때 사용하는 용어)로 옮긴다.

그리고 다 더하면 출력하고자 하는 값이 된다.

 

2. 제출 코드

// 1094번, 막대기

#include <stdio.h>

int main(void)
{
	int val;
	int ans;

	scanf("%d", &val);

	//64cm 막대기로 만들 수 있는 막대기의 길이: 64, 32, 16, 8, 4, 2, 1
	ans = ((val >> 6) & 1) // 막대기 64cm 사용 여부
		+ ((val >> 5) & 1) // 막대기 32cm 사용 여부
		+ ((val >> 4) & 1) // 막대기 16cm 사용 여부
		+ ((val >> 3) & 1) // 막대기 8cm 사용 여부
		+ ((val >> 2) & 1) // 막대기 4cm 사용 여부
		+ ((val >> 1) & 1) // 막대기 2cm 사용 여부
		+ ((val >> 0) & 1);// 막대기 1cm 사용 여부

	printf("%d\n", ans);

	return 0;
}