Question

What is the minimum number of bits needed to encode the days of the
month in a Canadian calendar.

	1.	5
	2.	3
	3.	6
	4.	4

Answer 1

Answer is 5 bits.

Consider the following case. You have to count whole numbers less than 4 in binary. A 1-bit binary can have 2 values exclusively., either 0 or 1. With 2 bits, we can have 4 possible combinatios.

Decimal Binary

1 bit can count - 2values - 0, 1 0, 1

2-bits can count - 4 values - 0,1,2,3 00, 01, 10, 11

n-bits can have - 2ⁿ combinations

So, Minimum 2 bits are required to count whole numbers less than 4. In other words, 2-bits are enough to encode numbers less than 4. The General formula is, to count a number X, select a power 'n' of 2 which is closer to x.

2ⁿ >=X

To count whole numbers less than 4, we need enough no. of bits which have 4 different combinations.

What about 4 included ? How many bits are required then ?

Now, we have to count 5 numbers(0,1,2,3,4). so we need to find the power of 2, 'n', closer to 5

2² < 5 .

2 bits are not enough to represent 5 numbers as it does not have 5 combinations

2³ > 5.

3 bits have 8 different combinations. So, with 3 bits we can count numbers till 2³-1 = 7 (0,1,2,3,4,5,6)

Even 4-bits can be used to count numbers less than 5.

0000 - 0

0001 - 1

0010 - 2

0011 - 3

0100 - 4

But the countable range of 4-bits is 2⁴ = 16. Infact any number of bits greater than 3 can be used to count numbers less than 5, but it is just waste of memory.

So, Minimum 3 -bits are required to count 5 numbers.(0,1,2,3,4)

Canadian Calendar:

Now, the Canadian Calendar has 31 days in Odd numbered months and 30 days in even numbered months, except for Febraury which can have either 28 or 29 days depending on its occurance in a Leap year, but No month will more than 31 days in a Calendar year.

2⁵ > 31

Hence minimum 5-bits are required to encode the days of a month in a Canadian Calendar.