[C] 19945번: 새로운 언어 CC

문제#

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

C언어는 int형 변수를 32개의 bit를 이용하여 2의 보수 방식을 따라서 이진수의 형태로 저장한다.

즉, 정수 10은 0000 0000 0000 0000 0000 0000 0000 1010으로 저장된다.

하지만 세상을 뒤흔들 새로운 언어 CC는 메모리를 줄이기 위해 int형 변수를 저장할 때 앞에서부터 연속된 0은 저장하지 않는다. 즉, 정수 10은 1010으로 저장된다. 그 외에 저장하는 방법은 C언어와 같다.

정수 n을 CC에 저장하는데 필요한 bit의 개수를 출력하여라. 단, n이 0일 때는 1개의 bit를 사용하여 0을 저장한다.

입력#

언어 CC에 저장할 n이 주어진다.

출력#

변수 n을 저장하는데 필요한 bit의 개수를 출력한다.

풀이#

이 문제는 정수 n을 2의 보수 형태로 저장할 때, 앞쪽의 연속된 0만 제거한다고 생각하면 됩니다.

경우를 나누면 다음과 같습니다.

• n == 0 이면 문제에서 특별히 0을 1비트로 저장하므로 답은 1
• n < 0 이면 2의 보수 표현에서 가장 앞 비트가 1이고, 앞의 0이 존재하지 않으므로 32비트 전체가 필요
• n > 0 이면 이진수로 표현했을 때 필요한 비트 수를 세면 됨

양수의 경우에는 n을 오른쪽으로 한 비트씩 밀면서 몇 번 이동하는지 세면 필요한 비트 수를 구할 수 있습니다.

제한#

• -2,147,483,648 ≤ n ≤ 2,147,483,647

코드#

1
#include <stdio.h>
2

3
int main() {
4
    int n;
5
    int count = 0;
6

7
    scanf("%d", &n);
8

9
    if (n == 0) {
10
        printf("1\n");
11
        return 0;
12
    }
13

14
    if (n < 0) {
15
        printf("32\n");
16
        return 0;
17
    }
18

19
    while (n > 0) {
20
        n >>= 1;
21
        count++;
22
    }
23

24
    printf("%d\n", count);
25
    return 0;
26
}