Binary Number System

Computers can only store 0s and 1s. There is no minus sign or decimal point inside a memory cell. So before we can understand how C stores numbers in a variable, we need to understand how numbers are written using only bits. Everything in Data Types And Variables builds on top of this note.

Bits, Nibbles and Bytes

• A bit is a single binary digit: either 0 or 1.
• A nibble is a group of 4 bits. It corresponds to exactly one hexadecimal digit.
• A byte is a group of 8 bits (two nibbles), and it is the smallest unit of memory a C program can address.

$1\text{ byte}=8\text{ bits}$

Since each bit can hold two values, a byte can hold $2^8=256$ distinct patterns. That single fact is where every data type range in C comes from.

Place Values (Positional Notation)

In the decimal system we use every day, each position is worth a power of 10. Binary works exactly the same way, except each position is worth a power of 2:

Bit position	7	6	5	4	3	2	1	0
Weight	128	64	32	16	8	4	2	1
Power of 2	$2^7$	$2^6$	$2^5$	$2^4$	$2^3$	$2^2$	$2^1$	$2^0$

To read a binary number, multiply each bit by its weight and add everything up:

$$v=\sum _{i=0}^{n-1}{b}_i\cdot 2^i=b_{n-1}\cdot 2^{n-1}+\cdots +b_1\cdot 2+b_0$$

where $b_i$ is the bit at position $i$.

Follow Along: Reading 0101 1010

Let’s decode the byte 0101 1010 bit by bit, using the table above. Write the byte under the weights, and multiply each column:

Weights:   128   64   32     16     8   4    2    1
Bits:        0    1    0      1     1   0    1    0
             ↓    ↓    ↓      ↓     ↓   ↓    ↓    ↓
Column:  0·128   1·64  0·32  1·16  1·8  0·4  1·2  0·1
                  ↓           ↓     ↓         ↓
                  64          16    8         2        → add them up

$$01011010_2=64+16+8+2=90_{10}$$

Notice the trick: a 0 bit contributes nothing, so you can simply add up the weights of the columns that contain a 1. You don’t even need to know which bit position each 1 is in. The weight is written right above it.

Your turn

Try 0010 0101 yourself before reading on.

The 1s sit under the weights $32$, $4$ and $1$:

$$00100101_2=32+4+1=37_{10}$$

If you got $37$, you can already read binary.

MSB and LSB

• The MSB (Most Significant Bit) is the leftmost bit. It has the largest weight ($2^7$ in a byte). In 0101 1010 the MSB is the first 0 (worth 128, and here it contributes nothing).
• The LSB (Least Significant Bit) is the rightmost bit. It has the weight $1$. In 0101 1010 the LSB is the final 0.
• A quick sanity check: flipping only the LSB can change the value by at most 1, while flipping only the MSB can change it by 128. That’s why they’re called most and least significant.

Converting Decimal to Binary

Method 1: Subtract the largest power of 2 (place-value method)

Find the biggest weight that fits, mark that bit 1, subtract, and repeat with the remainder.

Example: convert $25$ to binary.

$$25=16+8+1=2^4+2^3+2^0$$

Weights:  128  64  32  16  8  4  2  1
Bits:       0   0   0   1  1  0  0  1
                        ↑  ↑     ↑
                       16  8     1   → 16 + 8 + 1 = 25

So $25_{10}=00011001_2$ in one byte. Since 25 needs only 5 bits, the 3 unused leading bits are simply filled with 0.

Method 2: Repeated division by 2

Keep dividing by 2 and write down the remainders. Reading the remainders from bottom to top gives the binary number.

25 ÷ 2 = 12   remainder 1  ↑
12 ÷ 2 =  6   remainder 0  │ read
 6 ÷ 2 =  3   remainder 0  │ this
 3 ÷ 2 =  1   remainder 1  │ way
 1 ÷ 2 =  0   remainder 1  │
                           │
        result: 1 1 0 0 1  ┘

So $25_{10}=11001_2$.

Which method to use?

Method 1 is easier in your head for small numbers. Method 2 is mechanical and always works, even for big numbers.

Converting Binary to Decimal

Just apply the place-value formula. Example: what is 0001 1001?

Weights:  128  64  32  16  8  4  2  1
Bits:       0   0   0   1  1  0  0  1

value = 16 + 8 + 1 = 25

$$00011001_2=1\cdot 2^4+1\cdot 2^3+1\cdot 2^0=16+8+1=25_{10}$$

Hexadecimal: a Shorthand for Binary

Binary strings are long and easy to misread, so we often group bits into nibbles and give each nibble one hexadecimal (base-16) digit:

What Is a Base-16 Digit?

A base answers one question: how many distinct symbols do we have before we run out and carry to the next position?

• Base 10 (decimal): ten symbols, 0 to 9. We’ve used this since childhood, so it feels natural, but the choice of ten is arbitrary (probably just because we have ten fingers).
• Base 2 (binary): two symbols, 0 and 1. One bit per position.
• Base 16 (hexadecimal): sixteen symbols per position. But our digits stop at 9, so we’re six symbols short. So hexadecimal invents six extra digits by recycling the first letters of the alphabet:

$$\underset{\text{familiar digits}}{\underbrace{0,1,2,\dots ,9}},\underset{\text{digit stand-ins}}{\underbrace{A,B,C,D,E,F}}$$

Each letter is just a digit whose value we’d otherwise need two characters to write:

Hex digit	Value		Hex digit	Value
A	10		D	13
B	11		E	14
C	12		F	15

Nothing else changes. Hexadecimal is positional notation exactly like decimal, except each position is worth a power of 16 instead of a power of 10:

$$v=\sum _{i=0}^{n-1}{h}_i\cdot 16^i$$

Legend: what each symbol means

Symbol	Meaning
$v$	The final value of the number, in everyday decimal
$h_i$	The hex digit sitting at position $i$ (counting from the right, starting at 0)
$16^i$	The weight of that position. It is a power of 16, exactly like the weights 128, 64, 32 and so on in the binary table
${\sum }_{i=0}^{n-1}$	”Add up the following for every position $i$ from 0 up to $n-1$”. A fancy way of writing a running total
$n$	How many hex digits the number has

In words: multiply each digit by its weight, then add all the columns.

Follow Along: $0x2A$

The number 0x2A has two digits, so $n=2$. Rightmost digit is position 0:

Position i:     1    0
Digit h_i:      2    A
Weight 16^i:   16    1
               ────────
Column:       32   10     → add them up

$$v=\underset{32}{\underbrace{2\cdot 16^1}}+\underset{10}{\underbrace{10\cdot 16^0}}=42_{10}$$

Note that the letter digit A is substituted with its value $10$ before multiplying. Letters are just digits we hadn’t named yet.

Follow Along: Counting in hex

Just like 09 rolls over to 10 in decimal, 0x09 rolls over to 0x0A:

 0x08  =   8        0x0C  =  12        0x0F  =  15   ← F is the last symbol
 0x09  =   9        0x0D  =  13        0x10  =  16   ← carry: 1·16 + 0
 0x0A  =  10        0x0E  =  14        0x11  =  17   ← 1·16 + 1
 0x0B  =  11        0x0F  =  15        0x1F  =  31   ← 1·16 + 15

Why base 16 and not base 10?

Because $16=2^4$: one hex digit replaces exactly 4 bits, always. A byte is two hex digits, and a 16-bit value is four. The conversion is pure substitution, no arithmetic needed. Decimal has no clean relationship to powers of 2, which is why decimal and binary never line up.

Binary	Decimal	Hex		Binary	Decimal	Hex
0000	0	0		1000	8	8
0001	1	1		1001	9	9
0010	2	2		1010	10	A
0011	3	3		1011	11	B
0100	4	4		1100	12	C
0101	5	5		1101	13	D
0110	6	6		1110	14	E
0111	7	7		1111	15	F

In C, hexadecimal literals are written with a 0x prefix, e.g. 0x19. Each hex digit covers 4 bits, so one byte is always exactly two hex digits:

What Is the 0x?

The 0x is not part of the value. It’s a marker that tells the compiler to read the digits that follow in base 16. This matters because the digits themselves can be ambiguous:

19  →  is this nineteen?  or  1·16 + 9 = 25?

A bare 19 is decimal (nineteen) by default, so we need a way to switch bases. C’s rule is: the first digit must always be one of 0 to 9 (so the compiler can still recognize it as a number, not a variable name), and then a prefix selects the base:

Literal	Prefix	Base	Value (decimal)
25	(none)	10	25
0x19	0x	16	$1\cdot 16+9=25$
031	leading 0	8 (octal)	$3\cdot 8+1=25$
0b11001	0b	2 (GCC extension)	$16+8+1=25$

So 0x simply means: “hex follows”. The x itself stands for hexadecimal (in older literature you’ll also see it called hex, and the prefix is sometimes written 0X, where uppercase is identical in meaning).

The value doesn't change, only the notation

25, 0x19, 031 and 0b11001 all produce the same number in memory. The compiler converts them to identical bits. The prefix only changes how you wrote it down:

char a = 25;     // decimal
char b = 0x19;   // hexadecimal, same value as a
char c = 0b11001; // binary (GCC extension), also the same

Beware the leading-zero octal trap

A plain leading 0 (not 0x) means octal (base 8) in C. Writing 019 is not nineteen. It’s actually a compile error, since 9 is not a valid octal digit. This is why you should never pad decimal literals with zeros.

  0001 1001
    ↓    ↓
    1    9      →  0x19

And reading a hex number back into decimal uses powers of 16:

$$0x19=1\cdot 16^1+9\cdot 16^0=16+9=25_{10}$$

Quick check

0xE7 is 1110 0111 in binary, because E = 1110 and 7 = 0111. As a plain (unsigned) binary number that is $128+64+32+4+2+1=231$. Why this same byte can also mean $-25$ is explained in One’s and Two’s Complement.

Counting and the All Ones Trick

Two patterns show up constantly in C:

• All zeros is the smallest value a plain binary number can hold: $\underset{n}{\underbrace{00\dots 0}}=0$
• All ones is the largest value a plain binary number can hold:

$$\underset{n\text{ bits}}{\underbrace{11\dots 1}}=2^n-1$$

Why $2^n-1$? The odometer argument

Think of a car odometer with 3 digits. It can show $000$ through $999$. That’s $10^3=1000$ different readings. The highest reading is not $1000$ (it can’t show four digits), it’s $999=10^3-1$. The count is always one more than the highest value, because counting starts at zero.

Binary behaves identically. With 3 bits there are $2^3=8$ patterns, and counting runs from 0 up to the maximum:

 000 = 0     100 = 4
 001 = 1     101 = 5
 010 = 2     110 = 6
 011 = 3     111 = 7   ← largest = 2^3 - 1

Eight patterns, highest value 7, not 8. The pattern 000 spent one slot on zero. In general: $n$ bits give $2^n$ patterns, and since counting starts at 0, the largest is $2^n-1$. All-ones is simply the pattern that represents it.

You can see the same thing from the rollover: adding 1 to 111 cascades a carry through every bit and pushes out a 4th digit:

   1 1 1
 +     1
 -------
 1 0 0 0   ← = 8, but it needs a 4th bit

The result 1000 ($2^3$) doesn’t fit in 3 bits. So the largest number that does fit must be one less: $2^3-1=7$. For a byte, the same argument with $n=8$ gives $2^8-1=255$.

Key Formulas

Here is everything from this note on one card. The third row is the one that trips everyone up. It’s not a new idea, it’s just the Place Values rule from earlier written in symbols:

$$\sum _{i=0}^{n-1}{b}_i\cdot 2^i$$

Read it one piece at a time, right to left:

1. $2^i$ is the weight of position $i$ (position 0 is worth $1$, position 1 is worth $2$, position 2 is worth $4$, and so on).
2. $b_i\cdot 2^i$: take the bit at that position and multiply it by its weight. If the bit is 0, the column is worth nothing. If it’s 1, the column is worth exactly its weight.
3. ${\sum }_{i=0}^{n-1}$: add up all those columns, from position 0 up to position $n-1$ (the leftmost bit).

So the whole monster formula just says: each bit times its weight, all added up. That is the exact thing you did in Follow Along: Reading 0101 1010.

Question	Formula (for $n$ bits)	In plain words	Byte ($n=8$)
Number of distinct patterns	$2^n$	Every added bit doubles the count	$256$
Largest plain binary value	$2^n-1$	All bits set to 1	$255$
Value of a pattern	${\sum }_{i=0}^{n-1}{b}_i\cdot 2^i$	Multiply each bit by its weight and add, which means add the weights of the 1 bits	any $n$

Related: One’s and Two’s Complement explains how negative numbers fit into these bits, and Char Data Type shows where these formulas give the char ranges.