How many bits are necessary to encode an integer in the range of 0 to 31 (inclusive)?

Question

Can someone please explain how to approach a problem like this?

Answer 1

"Bits" are "binary digits". That means (by definition), they are digits in a base-2 number system. So instead of the base-10 system that you're used to (with digits 0-9 in each column), you only get two values (0 or 1) for each column.

Every column in a base-10 system corresponds to a power of 10 -- for example, 123 is 1 x 10^2 + 2 * 10^1 + 3 * 10^0.

Binary works the same way, except with base 2 instead of 10. So 10011 is 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 which is 19 in decimal.

Now, to figure out how many bits (i.e. digits) you need to represent a given number range, you can start with one bit and keep adding another until you have enough room. For example, 0-1 will fit in a single bit; 50 will require at least 6 bits, since 1 is only enough for 0-1, 2 bits is only enough for 0-3, 3 bits is only enough for 0-7, etc. until you get to 5 bits being only enough for 0-31, but 6 being more than enough.

Each additional bit doubles the quantity of possible numbers that can be represented by that many bits (just as adding another base-10 digit lets you represent ten times as many numbers). 0 bits can represent 0 numbers. 1 bit can represent 2 numbers (0-1). 2 bits can represent 2*2 numbers. 3 bits can represent 2*2*2 = 2^3 numbers. 4 bits can represent 2^4 numbers. And so on.

The only tricky thing left to consider is the distinction between the quantity of representable numbers, and the actual range that those representations correspond to. If you have, say, 4 bits, there are 2^4 different bit combinations (0000 to 1111). But if you consider 0000 to represent zero, then the largest number you can fit in four bits is 15 (not 16, since even though there's sixteen different possible representations, the range [0-15] comprises sixteen different numbers (count them!) and so 16 itself would be a 17th number, and thus would require 5 bits to represent).

I hope this clarifies things!

Answer 2

you need 5 bits. each bit can have one of two values, and the number of cominations of 5 bits is 2^5. You can show that 2^n is the number of combinations n bits by considering the base case:

1 bit = two possible choices = 2^1

and then the induction step.

if we have N bits, then we can divide this into 1 bit plus n-1 bit. if the formula is true, then there are 2^(n-1) combinations of the last n-1 bits, and for each of those combinations, the first bit can be in one of two positions. Hence, for N bits there are 2*(2^(n-1)) combinations, which is equal to 2^(n-1+1) which is equal to 2^n.

This is proof by induction. the first step is easy (n=1) and then the second step shows us that if it is true for n=1 then it is true for n=2, and then n=3 and then n=4, etc.

Answer 3

In binary, it's best to think of a column of 1s and 0s. Each column represents 2 raised to some power. You read from right to left, and farthest right is always 2 ^ 0 power, followed by 2 ^ 1, etc. etc.

When 2 ^ 0 is set to 0, you get a value of 0. When 2 ^ 0 is set to 1, you get a value of 1 (anything raised to the zeroth power is 1.)

Treat the binary 1 or 0 to mean it is on or off. You sum the "ons" by their respective outputs. Each column, or 0/1 value is represents a bit.

000000 = 0
000001 = 1
000010 = 2
000011 = 3
000100 = 4
000101 = 5
000110 = 6
000111 = 7

And so forth. Since 2^5 = 32, there would need to be a 1 in the 6th column, not the 5th. Since we start at the zeroth exponent.

100000 = 32, so 6 bits, but it was only inclusive of 31, so we have to go down one value.
011111 = 31, so 5 bits, are absolutely necessary for representing the number 31.