Binary, Octal, Decimal, Hexadecimal

notation
C notation
converting to decimal notation
converting between binary and octal
converting between binary and hexadecimal
converting between octal and hexadecimal
converting decimal to binary
representing negative numbers with two's complement

1. Notation

Numbers systems are based on powers. Decimal numbers use powers of 10 and the digits 0 to 9. The number 32761 is

32761 = 3 x 10⁴ + 2 x 10³ + 7 x 10² + 6 x 10 + 1

Binary numbers use powers of 2 and the digits 0 and 1. The binary number 101101 is

101101 = 2⁵ + 2³ + 2² + 1

You should memorize the initial powers of 2:

 N		2^N			 N	2^N
 0	        1			16	 64K
 1	        2			17	128K
 2	        4			18	256K
 3	        8			19	512K
 4	       16			20	  1M
 5	       32			21	  2M
 6	       64			22	  4M
 7	      128			23	  8M
 8	      256			24	 16M
 9	      512			25	 32M
10	     1024	   1K		26	 64M
11	     2048	   2K		27	128M
12	     4096	   4K		28	256M
13	     8192	   8K		29	512M
14	    16384	  16K		30	  1G
15	    32768	  32K		31	  2G
					32	  4G

To be precise, 4G is 4,294,967,296, which is 1 more than the largest, unsigned, 32-bit integer value.

Octal numbers use powers of 8 and the digits 0 through 7. The octal number 32761 is

32761 = 3 x 8⁴ + 2 x 8³ + 7 x 8² + 6 x 8 + 1

Hexadecimal (hex) numbers use powers of 16 and the digits 0 to 9, plus A through F (upper- or lowercase) for digits that represent 10 through 15:

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

The hexadecimal number CAFE is

CAFE = 12 x 16³ + 10 x 16² + 15 x 16 + 14

2. C notation

In C, character constants and file permissions are often expressed using octal notation. Bit vectors, memory locations, sizes and sundry other values are expressed using hexadecimal notation.

in C, octal constants start with a 0 -- 031 is the octal number that is 25 in decimal notation. (And so: why can't programmers tell Halloween (Oct 31) from Christmas (Dec 25)?) Hexadecimal contants start with 0x or 0X -- 25 in hexadecimal notation is 0x19. Binary constants cannot be expressed directly in C; use hexadecimal or octal notation instead.

3. converting to decimal notation

...was demonstrated in section 1. Expand the number and do the arithmetic. The octal number 32761 is

32761 = 3 x 8⁴ + 2 x 8³ + 7 x 8² + 6 x 8 + 1 = 13,809

4. converting between binary and octal

The trick is to use the "rule of threes". Given a binary number:

11010111110001

Group its digits in triplets, starting at the right:

11 010 111 110 001

Now convert each group of binary digits to an octal digit:

The previous example yeilds this conversion:

11 010 111 110 001
 3   2   7   6   1

To convert from octal to binary, reverse the process:

  3   2   7   6   1
011 010 111 110 001

5. converting between binary and hexadecimal

The trick is to use the "rule of fours". Given a binary number:

11010111110001

Group its digits in quads, starting at the right:

11 0101 1111 0001

Now convert each group of binary digits to a hexadecimal digit:

0000	0		1000	8
0001	1		1001	9
0010	2		1010	A
0011	3		1011	B
0100	4		1100	C
0101	5		1101	D
0110	6		1110	E
0111	7		1111	F

The previous example yeilds this conversion:

11 0101 1111 0001
 3    5    F    1

To convert from hexadecimal to binary, reverse the process:

   3    5    F    1
0011 0101 1111 0001

One reason that hexadecimal is a convenient notation for programmers is that, since four bits = 1 hexadecimal digit, then one byte = 2 hexadecimal digits. For example, the maximum value of an unsigned 32-bit integer is 4,294,967,295 in decimal notation (have you memorized that yet?), or 0xFFFF FFFF in hexadecimal notation. One more example: 0xCAFE F1D0 has the following byte values:

byte 3	0xCA
byte 2	0xFE
byte 1	0xF1
byte 0	0xD0

The extraction of byte values is trivial, but try to do that in decimal! The example number is 3,405,705,680. Good luck.

6. converting between octal and hexadecimal

Compose the previous two tricks! To convert the hexadecimal number 35F1 to octal:

   3   5   F   1
0011010111110001	<-- rule of fours
0  3  2  7  6  1	<-- rule of threes

7. converting decimal to binary

For small numbers, guess! Consider the decimal number 100. The largest power of 2 it contains is 64. 100-64 = 36. The largest power of 2 bounded by 36 is 32. 36-32 = 4, which is 100 in binary. Result: 100 = 64 + 32 + 4, which is 1100100 in binary.

For a larger decimal number like 32761, be methodical. Work from the least significant to most significant digit.

32761 is odd, meaning a final binary digit of 1. Halve it. (Discard remainder.)
16380 is even, meaning a final digit of 0. Halve it.
8190 is even, digit 0. Halve it.
4095 is odd, digit 1. Halve it.
2047 is odd, digit 1. Halve it.
1023 is odd, digit 1. Halve it.
511 is odd, digit 1. Halve it.
255 you should know is 11111111.

Put the digits together in the correct order: 11111111 1111001, or 01111111 11111001.

8. representing negative numbers with two's complement

None of the previous discussion considered negative numbers. The standard way to encode a negative number is to use two's complement. There are three steps to the encoding. To represent the decimal number -10 as an 8-bit binary number:

Convert 10 to binary, padding to 8 bits.
```
00001010
```
Invert the digits (This is called one's complement.) 1 becomes 0, and 0 becomes 1:
```
11110101
```
Add one. Recall how to add 1: overflow causes you to carry 1. In decimal 99+1=100. In binary 1111+1=10000.
```
11110110
```

What is the motivation for two's complement encoding? Two's complement reduces subtraction to addition. To subtract 100 - 10, we convert 100 to binary and then add it to the representation of -10:

01100100	 100
11110110	- 10
--------	----
01011010	  90

When a binary encoding may represent a negative number, we say it is signed, versus the default, unsigned case. How can you tell when a signed binary encoding does indeed represent a negative number? When the sign bit is on. The sign bit is the most significant digit. So 11110110 represents a negative number. How can you convert back? One way is to repeat the process: invert and add 1:

11110110
00001001	<-- invert
00001010	<-- add one

And the result is 10 in binary.

What is the two's complement representation of -1 as a 16-bit value?

00000000 00000001	1
11111111 11111110	one's complement
11111111 11111111	add one = two's complement

So -1 is always represented by "all bits on".

What are the biggest positive and negative values that can be represented as a signed 8-bit value? For the positive value, the sign bit must be off, meaning the largest value is 01111111, or 127. For the negative value, the largest value is 10000000, or -128. There is always this off-by-one descrepency between the min and max values.