Data Storage in Memory, Bits, and Bytes

This is a companion note to Lecture 0

You should read this note as additional information for Lecture 0. It’s specifically regarding the memory and storage section, where we thought additional details might be helpful.

Introduction

Have you really thought about what it means when we write something like this?

int product_cost = 888;

In short: we are asking the computer to store the value 888 somewhere in its memory. That sounds straightforward, but what does it mean to store a value in memory? For example: what is memory, how do values get stored, how does the computer represent the value, how does it know what the value is supposed to mean later on… man, so many questions.

Let’s go into a little more detail.

How Computer Memory Stores Things

Memory in your computer is, at a very high level, an extremely long list of small storage cells. Each cell can be in one of two states, which we call 0 and 1.

Each of these cells is called a bit. A bit is short for binary digit, and it is the smallest unit of data that we typically use to represent information in computing.

The simplified picture is something like this:

memory cell:  0  1  2  3  4  5  6  7
stored bit:   0  1  1  0  0  1  0  1

Each position represents one bit cell. The cells are arranged in a long sequence, and each cell stores either 0 or 1.

In actual memory, a bit is represented by a real electronic component, such as a cell in dynamic random-access memory, or DRAM.

Optional: How does a DRAM cell store one bit of information?

The electronics part here is optional and totally for the fun (?) of our CEG students.

A simple DRAM cell uses one transistor and one capacitor.

The labels in the diagram mean:

label:  DL          AL           M           C
role:   data line   access line  transistor  capacitor

The two parallel plates next to each other are the two plates of one capacitor. The transistor connects the data line to the capacitor when the access line is activated.

In this simplified model, a charged capacitor represents 1, while a discharged capacitor represents 0:

state:      no charge  charged
bit value:  0          1

The important idea is that a computer does not have a magical box labelled “the number 888”. It has a large collection of bits, and some collection of those bits is used to represent the value.

How Bits Represent Useful Data

A sequence of bits does not have a meaning by itself. The same sequence of bits can represent different things depending on how we interpret it.

For example, a sequence might be interpreted as:

• an integer
• a character
• part of a fractional number
• an instruction for the processor (i.e.,, code!)

The type of a C variable helps tell the compiler how to interpret the bits. The simplest place for us to start is looking at how bits represent integers.

Counting in Binary

The numbers that you are used to are written in base 10, or decimal. We have ten possible digits, from 0 to 9, and each position represents a power of 10.

Binary is the base-2 number system. It has only two possible digits, 0 and 1.

Let’s try counting with three bits:

binary:   000  001  010  011  100  101  110  111
decimal:    0    1    2    3    4    5    6    7

Notice what happened when we counted from 011 to the next value. The rightmost bit could not increase any further, so it became 0 and the next bit became 1. This is the same carrying idea that happens when we count from 099 to 100 in decimal.

The Place Values of Binary

To convert a binary number to decimal, add up the powers of two in all the positions containing a 1.

Number the bit positions starting from 0 at the rightmost bit:

bit position:  7    6    5    4   3  2  1  0
power of two:  2^7  2^6  2^5  2^4  2^3  2^2  2^1  2^0
value:         128   64   32   16    8    4    2    1

For example, consider the eight-bit pattern $10000001_2$:

bit position:  7  6  5  4  3  2  1  0
bit:            1  0  0  0  0  0  0  1
contribution: 128  0  0  0  0  0  0  1

Only bit 7 and bit 0 are set to 1, so:

$$10000001_2=2^7+2^0=128+1=129_{10}$$

The subscripts are there to make the bases explicit. $10000001_2$ is a binary number, while $129_{10}$ is a decimal number.

This is the pattern behind the way computers represent integers. The computer stores the bits, and the chosen interpretation tells us how to read them.

Actually

The sequence 10000001 does not inherently mean 129. It means 129 when we interpret it as an unsigned binary integer. Give those same bits a different type or a different convention, and they can represent something else.

How Many Values Can We Represent?

Suppose we have one bit. It can contain either 0 or 1, so it can represent two unique values.

With two bits, we have four possible patterns:

00   01   10   11

With three bits, we have eight possible patterns. Each time we add one more bit, every existing pattern can be paired with both 0 and 1.

That gives us the general rule:

$$N\text{ bits can represent }{2}^N\text{ unique values}$$

number of bits:  1       2       3       8
unique patterns: 2^1=2   2^2=4   2^3=8   2^8=256

Eight bits are also called one byte. Therefore, one byte can represent 256 unique patterns.

For an unsigned integer, those patterns are usually read as values from 0 through $2^N-1$. An unsigned eight-bit value therefore ranges from 0 through 255.

Actually

The statement about $2^N$ unique values is about the number of available patterns. Signed integers need an additional convention for deciding which patterns represent negative values. In modern systems, signed integers use two’s complement for this purpose.

Optional: Two's Complement

Two’s complement is the usual way to interpret an N-bit pattern as a signed integer. The leftmost bit has weight $-2^{N-1}$; the remaining bit positions have the usual positive powers of two.

For eight bits, the pattern $10000001_2$ represents:

$$-2^7+2^0=-128+1=-127$$

This convention gives an N-bit signed integer the range from $-2^{N-1}$ through $2^{N-1}-1$. It is the extra convention that lets some bit patterns represent negative values.

From Bits to C Types

When we write a C declaration, we are asking the compiler to reserve memory and to treat the bits in a particular way.

int product_cost = 888;

The type int tells us that product_cost is intended to hold an integral value. The compiler chooses a suitable representation and reserves enough bytes for that type on the target system.

The same bits can give different results when interpreted as different types. For example, an unsigned int uses the available patterns only for non-negative values, while a signed int uses some patterns for negative values as well.

The following is the numerical-type summary from the lecture. The size column gives the minimum size guaranteed by C. The value columns reproduce the ranges shown on the slide, and other implementations may support wider ranges.

Type name(s)	Minimum value	Maximum value	Size: Number of bytes
char	-128	+127	Exactly 1 (8 bits)
unsigned char	0	+255	Exactly 1 (8 bits)
int	-32768 (-2^15)	+32767 (2^15 - 1)	Minimum 2 (16 bits)
unsigned int	0	+65535 (2^16 - 1)	Minimum 2 (16 bits)
long	-2147483648 (-2^31)	+2147483647 (2^31 - 1)	Minimum 4 (32 bits)
unsigned long	0	+4294967295 (2^32 - 1)	Minimum 4 (32 bits)

The type char can technically be either unsigned char or signed char, depending on the implementation. In the CS1010 environment, it is signed and ranges from -128 to +127.

There is also short (no larger than int, but often smaller) and (unsigned) long long, which provides at least 64 bits. Use double for values with decimal points unless you have a good reason to use float.

The larger point is that a type is not merely a funny label attached to a variable. The type of a variable tells the compiler how much storage is needed and how the stored bit pattern should be interpreted when the program reads it back.

The Main Ideas

When a C program creates a variable:

1. The computer reserves some memory for the variable
2. That memory contains a sequence of bits, grouped into bytes
3. The value is encoded as a pattern of 0s and 1s
4. The variable’s type tells the program how to interpret that pattern

So when we say that the computer stores 888, the computer is really storing a particular pattern of bits. The number 888 is the meaning we assign to that pattern when we interpret it as an int.