수와 표현

비트

0과 1을 표현할 수 있다. k 개의 비트를 사용하면 2^k개의 숫자를 표현할 수 있으며 0부터 표현한다고 했을 때 2k^-1까지 표현 가능하다.

문제

어떤 수 n을 표현하기 위해 최소 몇 개의 비트(k)를 사용해야하는가?

2^k-1>=n 또는 2^k>=n+1 를 만족해야하므로 k로 나타내면 다음과 같다.

k>=log2(n+1)≒log2(n)

문제 풀이

Q1) 2진수 표현에서 logN 비트로 표현할 수 있는 숫자 범위는?

logN=k라고할 때 2^k-1까지 표현할 수 있다. 2^logN-1이므로 N-1까지의 수를 표현할 수 있다.

Q2) 스무고개가 이상적으로 진행된다고 할 때, 맞출 수 있는 답의 종류는 몇 가지인가?

한 질문 당 2개의 답의 종류를 말할 수 있다. 맞출 수 있는 답의 종류는 2^20가지이다.