Bits, Bytes, Nybbles

The most important base you need to know for computer organization is base 2. We also call this binary, since binary means two valued.

The second most important base is base 16 (or hexadecimal), and the third is base 8 (octal). Beyond that, you don't need to know the other bases.

Let's start with some definitions first.

The definition of "word" isn't set. It has usually referred to the number of bits used in a register. These days, typical registers store 32 bits. However, already 64 bit architectures are being built (and have been for a few years). Throughout the class notes, we'll define a word to be 32 bits.

In base 2, we refer to the individual 1's and 0's as bits, rather than digits. This is very common terminology, so from now on, we won't refer to them as digits.

Labelling Individual Bits

As we saw in Converting from Base 10 to Base K, it's convenient to label individual digits, so we can refer to them by name. We'll label bits as well, from right to left, with 0 being the index of the rightmost bit.

For example, suppose you have an N-bit number. It would be written as: bN-1 bN-2...b1b0.

It's common to define two more terms for an N-bit number.

The reason it's called "least significant" bit is because the bit is associated with the smallest subscript, i.e., the smallest power of 2. Flipping this bit (i.e., changing it from 0 to 1, or 1 to 0) would affect the overall value the least of any bit that one could flip.

The reason it's called "most significant" bit is because the bit is associated with the largest subscript, i.e., the largest power of 2. Flipping this bit (i.e., changing it from 0 to 1, or 1 to 0) would affect the overall value the most of any bit in the number.

Bitstrings and Bit vectors

While there are standard sizes for differing number of bits (bits, bytes, nybbles, etc.), sometimes you just need to refer to a more arbitrary set of bits. We'll refer to a "N" bits as a bitstring or a bit vector.

It may seem odd to refer to a number as a string, but it's not so unusual. When you write numbers, you typically increase the number of digits as needed. Thus, you write 10, instead of 0010. However, in hardware, you often have a fixed number of bits, such as 16 bits or 32 bits. Leading zeroes will always appear to pad it to the necessary number of total bits.

So, the name "bit string" might be just as good any because it may imply a length of a string.

Bitstrings are also called bit vectors. In this case, a vector typically means a "coordinate" with N arguments. For example, when you study graphs in 2 or 3 dimensions, coordinates are written like (2,3) or (2,3,1). So 0010 could be thought of as (0,0,1,0), i.e. a coordinate in four dimensions.

Of course, when people talk about bit vectors, they're generally not thinking about it as a coordinate. The main point is that, unlike sets, vectors have numbered positions (though typically, vectors are numbered left to right, starting at index 1).

In any case, I will usually call it "bit strings".

How Many Different Bitstring Patterns?

Suppose you have an N-bit bitstring. How many possible patterns of 1's and 0's are there? And why do you care?

Let's answer the first question, first. To compute the number of N-bit bitstrings, realize that you have 2 choices for each bit. You simply multiply 2, N times. This is, of course, NOT the same thing as 2N. Instead, it is 2N.

This is a very important fact to remember, because the number of bitstring patterns limits the number of possible values that the bitstrings can represent.

For example, if you have 3 bits, then you have 8 possible bitstring patterns (since 8=23). That limits you to a maximum of 8 different values.

You may wonder why the number of bitstring patterns isn't the same as the number of values. We're going to see some examples where two different bitstring patterns correspond to the same number.

For example, I could make up a weird system where all 3-bit values really stand for 0. This wouldn't make much sense, but it doesn't necessarily have to. The number of possible representations does NOT have to equal the number of possible values.

The best we can say is that the number of different patterns forces a maximum on how many values those patterns can represent.

How many bits To Label N different items?

This is also an odd question. But let's see where it leads us. Suppose you have N different items. You wish to label them with an K bit binary number. What's the minimum number bits necessary?

We know that if we have K bits, then there are 2K different bitstring patterns. Thus, we want to solve:

2K >= N

To solve this, we take lg of both sides (this is log base two).

lg( 2K ) >= lg( N )

which simplifies to:

K >= lg( N )

which we can write as

K = ceil( lg( N ) )

The ceiling of X is the integer value Y such that Y - 1 < X <= Y. Thus, you round X up to the next highest integer, unless X is already an integer.

Why is this problem important? In a CPU, we will need to find some way to identify registers. Since computers manipulate 0's and 1's, we assign each register to a unique binary number.

Thus, if we have 32 registers, we assign each register a ceil( lg( 32 ) ) = 5 bit number. If the number of registers is not a power of 2, say, there are 12 registers, then we use ceil( lg( 12 ) ) = 4 bits.

In particular, we usually assign the registers an unsigned binary number starting at 0 and ending at N - 1.

For 12 registers, we assign 0000two (which is 0ten) up to 1011two (which is 11ten). The other four bitstring patterns (from 1100two to 1111two) are unused.

So if you're asked how many bits does it take to identify N different items, the answer is the ceiling of the lg (base two) of N.

This is one of those REALLY IMPORTANT FACTS (TM) that you should know.

Web Accessibility