Bits Needed

Q: How many bits do I need for one item?

Zero bits, because $\lceil \log_2 1 \rceil = 0$. There is nothing to tell apart. Real systems often still use at least one bit for such a field.

In one sentence: This formula counts the fewest bits you need so that every one of N items gets its own pattern of 0s and 1s.

$b = \lceil \log_2 N \rceil$

Read it out loud: “b equals the ceiling of the base-2 logarithm of N. b is the number of bits needed, always a whole number. N is how many different items need their own code. The base-2 logarithm of N is the power you must raise 2 to in order to get N. The ceiling is the pair of brackets with the top and bottom edges cut off, and it means round up to the next whole number.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Powers of two and counting patterns: A power of two is 2 multiplied by itself a set number of times. $2^{1} = 2$ , $2^{2} = 4$ , $2^{3} = 8$ and $2^{10} = 1024$ . Each extra bit doubles the number of patterns you can make. One bit makes 2 patterns, 0 and 1. Two bits make 4 patterns: 00, 01, 10 and 11. With $b$ bits there are $2^{b}$ patterns in all.
The base-2 logarithm, $\log_2$: The base-2 logarithm of a number $N$ , written $\log_2 N$ , is the power you must raise 2 to in order to get $N$ . So $\log_2 8 = 3$ , because $2^{3} = 8$ . For a number that is not a power of two, the answer is a decimal. For example $\log_2 1000 \approx 9.966$ , because $2^{9} = 512$ is too small and $2^{10} = 1024$ is big enough.
The ceiling, $\lceil x \rceil$: The ceiling of $x$ , written with brackets whose top edges are cut off, is $x$ rounded up to the next whole number. So $\lceil 9.97 \rceil = 10$ . The opposite, the floor, rounds down. Bits come only in whole numbers, so a count of bits that is 9.97 must become 10 bits, never 9.
At least, $\geq$: The sign $\geq$ means greater than or equal to. The statement $2^{b} \geq N$ says that the number of patterns, $2^{b}$ , is at least as big as the number of items $N$ . It may be bigger, which leaves spare patterns, but it must never be smaller, or some item would have no code.
Codes, bits and bytes: A code is a label made of bits, such as 1011, that names one item. Two items must never share the same code, so each code has to be different. A bit is one 0 or 1. A byte is a group of 8 bits, so 10 bits are not 10 bytes. Ten bits fit inside two bytes, with room to spare.

What each symbol means

Symbol	Meaning
$b$	The number of bits needed for the codes. It is always a whole number with no unit, because bits come in whole units. For 1000 products it is $b = 10$ bits.
$N$	How many different items need their own code. It is a count with no unit. A shop with 1000 different products has $N = 1000$ , and each product must have its own code.
$\log_2 N$	The base-2 logarithm of $N$ : the power you raise 2 to in order to get $N$ . It has no unit. For $N = 8$ it is 3, and for $N = 1000$ it is about 9.966.
$\lceil x \rceil$	The ceiling of $x$ : the number $x$ rounded up to the next whole number. It has no unit. For example $\lceil 9.966 \rceil = 10$ , because the ceiling always takes the next whole number above.

The formula piece by piece

$2^{b}$: The number of different patterns that $b$ bits can make. Each bit doubles the count, so 10 bits make $2^{10} = 1024$ patterns and 9 bits make $2^{9} = 512$ .
$2^{b} \geq N$: The rule the codes must follow. The number of patterns must be at least the number of items, so that every item can have its own pattern. Patterns may be left over, but there must never be too few.
$b \geq \log_2 N$: The same rule solved for $b$ . Taking the base-2 logarithm of both sides turns the question of powers into a question about the power itself: how many bits, at least, do we need? The answer may be a decimal such as 9.966.
$\lceil \log_2 N \rceil$: Round the decimal up to the next whole number. Bits are whole, and rounding up keeps the rule $2^{b} \geq N$ true. Rounding down would break it, because too few patterns would exist.
$b = \lceil \log_2 N \rceil$: The whole formula in one sentence: the number of bits needed equals the base-2 logarithm of the number of items, rounded up to a whole number of bits.

What the formula is doing, and why

What goes in and what comes out. You give the formula one number, $N$ , which is how many different items need their own code. It returns $b$ , the fewest bits that can give each item its own pattern of 0s and 1s. The answer is always a whole number, because a code is made of whole bits.

Why powers of two? Each extra bit doubles the number of patterns. One bit gives 2 patterns, two bits give 4, and three bits give 8. With $b$ bits there are $2^{b}$ patterns in all. To give $N$ items their own codes, we need $2^{b} \geq N$ , so that there are at least as many patterns as items.

Why take a logarithm and round up? Taking the base-2 logarithm of both sides of $2^{b} \geq N$ gives $b \geq \log_2 N$ . The logarithm can be a decimal, but $b$ must be a whole number of bits. So we round up with the ceiling. Rounding down would leave too few patterns: $\log_2 1000 \approx 9.966$ rounds down to 9 bits, and 9 bits give only 512 codes for 1000 items.

Counting labels, not digits. The codes are usually numbered from 0 up to $N - 1$ , and the only requirement is enough patterns. The formula counts labels, not the digits needed to write the number $N$ itself. Some patterns may stay unused, which is normal. A set of 1000 items uses 10 bits, which gives 1024 patterns and leaves 24 of them unused.

An everyday picture

Think of a row of light switches on a wall. Each switch is one bit, and each one is either on or off. Three switches give $2^{3} = 8$ different on-off patterns, so eight guests can each have their own pattern. A ninth guest needs a fourth switch, because three switches cannot make a ninth different pattern.

Worked example: Coding 1000 products

A shop has $N = 1000$ different products, and each product needs its own binary code. We want the fewest bits per code, because shorter codes take less space on labels and in the shop’s database.

Take the base-2 logarithm. We ask how many times 2 must be multiplied by itself to reach 1000. The answer is $\log_2 1000 \approx 9.966$ . It lies between $2^{9} = 512$ and $2^{10} = 1024$ , so it is a little under 10.
Round up with the ceiling. Bits come in whole numbers, and the codes must have enough patterns, so we round up: $\lceil 9.966 \rceil = 10$ bits. Rounding down would give 9 bits, and 9 bits are not enough for this shop, as the next two steps show.
Check 9 bits. Nine bits give $2^{9} = 512$ patterns. Since 512 is less than 1000, nine bits cannot give every product its own code. Some products would have to share a code, and the shop needs every product to have a code of its own.
Check 10 bits. Ten bits give $2^{10} = 1024$ patterns. Since 1024 is at least 1000, every product can have its own code. The 1000 codes can be numbered 0 to 999, and the rest of the patterns are not needed.
Count the spare codes. The number of spare codes is $2^{10} - 1000 = 1024 - 1000 = 24$ . These 24 patterns are not used by any product yet, so the shop can keep them for new products later.

Answer: Each product needs 10 bits. Ten bits give 1024 codes, which covers the 1000 products with 24 codes to spare.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Rounding down. The floor of $\log_2 1000$ is 9, but 9 bits give only 512 codes. Always round up with the ceiling.
Adding 1 to $N$ when $N$ is a power of two. Eight items need $\lceil \log_2 8 \rceil = 3$ bits, since $2^{3} = 8$ . Using $N + 1 = 9$ would wrongly give 4 bits.
Using the natural logarithm, written $\ln$ . $\ln 1000 \approx 6.9$ gives the wrong answer. The formula needs the base-2 logarithm, $\log_2$ .
Confusing bits with bytes. The answer 10 is a count of bits, not bytes. Ten bits is not ten bytes, and it fits inside two bytes.

Where you will meet it

Color depth in images, where 8 bits per color channel give $2^{8} = 256$ levels each for red, green and blue.
Network packet fields, such as the 12-bit VLAN ID field in Ethernet frames, which has 4096 possible values.
Analog-to-digital converters, where a 10-bit converter can output 1024 different levels.
Database and program design, where a field with 16 categories needs $\lceil \log_2 16 \rceil = 4$ bits.

Questions people ask

Why round up instead of to the nearest whole number?

A code needs enough patterns. Rounding to the nearest whole number can round down. For example, $\log_2 600 \approx 9.23$ would round to 9, which gives only 512 codes for 600 items. Rounding up always gives enough patterns.

Is this the same as the number of bits needed to write $N$?

Not always. The formula counts codes for items numbered 0 to $N - 1$ . Writing the number $N$ itself can need one more bit. The number 1024 needs 11 bits to write in binary, but 1024 items need only 10 bits, since their codes run from 0 to 1023.

How many bits do I need for one item?

Zero bits, because $\lceil \log_2 1 \rceil = 0$ . There is nothing to tell apart. Real systems often still use at least one bit for such a field.

Binary Number Value: Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.
Shannon Entropy: Shannon entropy is one number, measured in bits, that says how unpredictable a source of messages is on average: the more predictable it is, the fewer bits its messages need.
Two's Complement: Two’s complement is the usual way computers write negative whole numbers in binary, and this formula reads a bit pattern as a positive or negative number.
Hexadecimal Number Value: Hexadecimal counts in sixteens using the digits 0 to 9 and the letters A to F, and this formula turns a hex number into the ordinary number it stands for.