## 4.2. Converting Between Bases

You’re likely to encounter each of the three number bases we’ve introduced in this chapter in different contexts. In some cases, you may need to convert from one base to another. This section starts by showing how to convert between binary and hexadecimal, since those two map easily to one another. After that, we’ll explore conversions to and from decimal.

### 4.2.1. Converting between Binary and Hexadecimal

Because the bases for both binary and hexadecimal are powers of 2, converting between the two is relatively straightforward. Specifically, each hexadecimal digit holds one of 16 unique values, and four bits also represents 24 = 16 unique values, making their expressive power equivalent. Table 1 enumerates the one-to-one mapping between any sequence of four bits and any single hexadecimal digit.

Table 1. The correspondence between all four-bit sequences and one-digit hexadecimal numbers.

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

Note that Table 1's content is equivalent to simply counting from 0 to 15 in both number systems, so there’s no need to memorize it. Armed with this mapping, you can convert any number of consecutive bits or hex digits in either direction:

• Converting 0xB491 to binary, simply substitute the corresponding binary value for each hexadecimal digit:

```  B    4    9    1
1011 0100 1001 0001  ->  0b1011010010010001```
• Converting 0b1111011001 to hexadecimal, first divide up the bits into chunks of four, from right to left. If the leftmost chunk doesn’t have four bits, you can pad with leading zeroes. Then, substitute the corresponding hexadecimal value:

```1111011001  ->  11 1101 1001  ->  0011 1101 1001

0011 1101 1001
3    D    9  ->  0x3D9```

### 4.2.2. Converting to Decimal

Fortunately, converting values to decimal is what we’ve been doing throughout previous sections of this chapter. Given a number in any base B, labeling the digits from right to left as d0, d1, d2, etc. enables a general formula for converting values to decimal:

(dN-1 * BN-1)    +    (dN-2 * BN-2)    +    …​    +    (d2 * B2)    +    (d1 * B1)    +    (d0 * B0)

### 4.2.3. Converting from Decimal

Converting from decimal to other systems requires a little more work. Informally, the goal is to do the reverse of the formula above: determine the value of each digit such that, based on the position of the digit, adding each term results in the source decimal number. It may help to think about each digit in the target base system in the same way that we described the places (e.g., "ones place", "tens place", etc.) for decimal. For example, consider converting from decimal to hexadecimal. Each digit of a hexadecimal number corresponds to an increasingly large power of 16, and Table 2 lists the first few powers:

Table 2. Powers of sixteen.
164 163 162 161 160

65536

4096

256

16

1

For example, to convert 9742 to hexadecimal, consider:

How many multiples of 65536 fit into 9742? (i.e., what is the value of the "65536’s place"?)

• The resulting hexadecimal value doesn’t need any multiples of 65536, since the value (9742) is smaller than 65536, so digit4 should be set to 0. Note that by the same logic, all higher-numbered digits will also be 0, since each digit would contribute values even larger than 65536. Thus far, the result contains only:

 0 d4 d3 d2 d1 d0

How many multiples of 4096 fit into 9742? (i.e., what is the value of the "4096’s place"?)

• 4096 fits into 9742 twice (2 * 4096 = 8192), so the value of digit3 should be 2. Thus, digit3 will contribute 8192 to the overall value, so the result must still account for 9742 - 8192 = 1550.

 0 2 d4 d3 d2 d1 d0

How many multiples of 256 fit into 1550? (i.e., what is the value of the "256’s place"?)

• 256 fits into 1550 six times (6 * 256 = 1536), so the value of digit2 should be 6, leaving 1550 - 1536 = 14.

 0 2 6 d4 d3 d2 d1 d0

How many multiples of 16 fit into 14? (i.e., what is the value of the "sixteens place"?)

• None, so digit1 must be 0.

 0 2 6 0 d4 d3 d2 d1 d0

Finally, how many multiples of 1 fit into 14? (i.e., what is the value of the "ones place"?)

• The answer is 14, of course, which hexadecimal represents with the digit `E`.

 0 2 6 0 E d4 d3 d2 d1 d0

Thus, decimal 9742 corresponds to 0x260E.

#### Decimal to Binary: Powers of Two

The same procedure works for binary as well (or any other number system), provided that you use powers of the appropriate base. Table 3 lists the first few powers of two, which will to help convert the example decimal value 422 to binary.

Table 3. Powers of two.
28 27 26 25 24 23 22 21 20

256

128

64

32

16

8

4

2

1

Since an individual bit is only allowed to store a 0 or 1, the question is no longer how many multiples of each power fit within a value when converting to binary. Instead, ask a simpler question: does the next power of two fit? For example, in converting 422:

• 256 fits into 422, so d8 should be a 1. That leaves 422 - 256 = 166.

• 128 fits into 166, so d7 should be a 1. That leaves 166 - 128 = 38.

• 64 does not fit into 38, so d6 should be a 0.

• 32 fits into 38, so d5 should be a 1. That leaves 38 - 32 = 6.

• 16 does not fit into 6, so d4 should be a 0.

• 8 does not fit into 6, so d3 should be a 0.

• 4 fits into 6, so d2 should be a 1. That leaves 6 - 4 = 2.

• 2 fits into 2, so d1 should be a 1. That leaves 2 - 2 = 0. (Note: upon reaching 0, all remaining digits will always be 0.)

• 1 does not fit into 0, so d0 should be a 0.

Thus, decimal 422 corresponds to 0b110100110.

#### Decimal to Binary: Repeated Division

The method described above generally works well for students who are familiar with the relevant powers of two (e.g., for 422, the converter must recognize that it should start at d8 because 29 = 512 is too large).

An alternative method doesn’t require knowing powers of two. Instead, this method builds a binary result by checking the parity (even or odd) status of a decimal number and repeatedly dividing it by two (rounding halves down) to determine each successive bit. Note that it builds the resulting bit sequence from right to left. If the decimal value is even, the next bit should be a zero, and if it’s odd, the next bit should be a one. When the division reaches zero, the conversion is complete.

For example, when converting 422:

• 422 is even, so d0 should be a 0. (rightmost bit)

• 422 / 2 = 211, which is odd, so d1 should be a 1.

• 211 / 2 = 105, which is odd, so d2 should be a 1.

• 105 / 2 = 52, which is even, so d3 should be a 0.

• 52 / 2 = 26, which is even, so d4 should be a 0.

• 26 / 2 = 13, which is odd, so d5 should be a 1.

• 13 / 2 = 6, which is even, so d6 should be a 0.

• 6 / 2 = 3, which is odd, so d7 should be a 1.

• 3 / 2 = 1, which is odd, so d8 should be a 1.

• 1 / 2 = 0, so any digit numbered nine or above will be 0, and the algorithm terminates.

As expected, this method produces the same binary sequence: 0b110100110.