Binary, Decimal, Hex

1Learning Outcomes¶

• Translate between binary, decimal, and hexadecimal number representations

• Use hexadecimal as shorthand for binary

• Know when each representation is useful

2Introduction¶

In this section, we discuss how computer architects and computer scientists translate between the rich world that humans see and information that computers store. The former is framed by how humans think—after all, we have ten fingers, also known as “digits”. The latter is in bits.

3Numerals as a representation of Numbers¶

Let’s discuss the idea of formally representing a number with many possible numerals, i.e., symbols.

• Numeral: A symbol (or series of symbols) or name that stands for a number, e.g., 4 , four , quatro , IV , IIII , …. Numerals are composed of multiple symbols called digits.

• Number: The “idea” in our minds, e.g., the concept of “4”. There is only ONE concept of a number, but there can be many possible numeric representations via many possible numerals.

Figure 2 is a motivating (and humorous) example. An alien and an astronaut are discussing how to represent the number of rocks in a pile.

The alien, the astronaut, and the pile of rocks use three different representations of the number four. The astronaut uses the numeral 4 to represent four as a base-10 integer. The alien uses the numeral 10 to represent four as a base-4 integer. The pile of rocks uses four rocks to represent four as, well, a pile of rocks.

4Binary, Decimal, and Hexadecimal Representations¶

While there are an infinite number of bases with which to represent numbers, we discuss three will be the most useful to us, as computer scientists: decimal, binary, and hexadecimal representations.

Table 1 probably makes little sense to you at the moment, but we present it first so you can make some educated guesses.

4.1Decimal: Base 10 (Ten) Numbers¶

First, consider decimal numerals. The decimal numeral 3271 is written in that order, because it describes how to count powers of ten corresponding to the equation below (note the superscript 10 denotes a base-10 numeral):

Each of the four digits specify a count of a power of ten. We add these up to get the number three thousand, two hundred seventy-one.

This process will seem natural to you—because we humans think in base ten—but we will see that we can apply this understanding to represent numbers in other bases. Nevertheless, we highlight a few implicit assumptions:

• For now, we only consider powers of 10 needed to compose non-negative integers; we will discuss how to represent fractions later. The smallest such power of 10 is $10^0 = 1$.

• The “largest” power of 10 for this number can be more precisely defined as the largest power of 10 corresponding to a non-zero digit. In other words, the decimal $0 \dots 03271$ with leading zeros (on the left) and the decimal 3271 represent the same number.

• Base ten uses the ten digits 0 to 9 to create unique decimal representations. In other words, to form the decimal 10, instead of using ten of 10⁰, we use one 10¹ and zero 10⁰. Wikipedia provides a more formal discussion of uniqueness.

4.2Base 2 (Two) Numbers, Binary¶

Binary numbers like 1101 are written in that order to describe how to count powers of two. Notably, the two binary digits, 0 and 1, are the namesake of the bit (which takes on those two values).

What does the binary numeral 1101 represent?

Because humans think in decimal, we convert this binary value to decimal with a similar process as above:

Other notes:

• We prepend the prefix 0b to denote that the numeral 1101 should be interpreted in base 2; the shorthand 0b1101 is equivalent to the mathematical notation 1101₂ but can be written with a standard keyboard.

• Like before, 0b0...01101 and 0b1101 represent the same nunber, thirteen.

• Because there are just two binary digits 0 and 1, in binary we are always either including a value (here, a specific power of two), or not including it. 1 or 0, True or False. This idea of binary representing “inclusion” or “exclusion” will show up repeatedly in this course.

4.3Base 16 (Sixteen) #s, Hexadecimal¶

Finally, we consider hexadecimal numbers.

What does the hexadecimal numeral A5 represent?

Convert to decimal:

We prepend the prefix 0x to denote that the numeral A5 should be interpreted in base 16. Like before, the shorthand 0xA5 is equivalent to $A5_{16}$ but can be written with a standard keyboard.

Hexadecimal digits are useful as shorthand for representing groups of four binary digits. We discuss more at the end of this section.

5Convert between representations¶

Let’s discuss conversion in more detail. We only consider “unsigned” numerals, i.e., non-negative numbers.

If we have an $n$-digit unsigned numeral $d_{n-1}$ $d_{n-2}$...$d_0$ in radix (or base) $r$, then the value of that numeral is:

which is just fancy notation to say that instead of a 10’s or 100’s place we have an $r$’s or $r^2$’s place. For the three radices binary, decimal, and hex, we just let $r$ be 2, 10, and 16, respectively.

5.1Decimal $\rightarrow$ Binary¶

The slidedeck below shows how we can convert the decimal 13 into its binary representation, 0b1101.

Let val be 13 in the explanation below. Click to show.

The process above relies on a few colloquial observations:

• The largest power of two we could possibly need is less than the number val itself.

• The smallest power of two we could possibly need is always the zero-th power, i.e., $2^0 = 1$.

• Start with larger power of twos first. Otherwise you may run into scenarios where you count beyond the number of digits available (here, only 0 and 1).

Here is one attempt at colloquially describing the algorithm to convert a number val into its binary representation:

• Make a set of columns, one for each power of two. This corresponds to your $n$-digit binary number, e.g., 0b _ _ ... _ _, with $n$ blanks.

• Start from the leftmost column and go right (i.e., for $i$ from $n-1$ to 0, inclusive):

  • For the current column $i$, corresponding to $2^i$:

    • Is the current column less than or equal to val?

      • If yes, count how many $2^i$ fit into val. For base 2, the count is 1, so subtract $1 \times 2^i$ from val. Keep going.

      • If no, put 0 and keep going.

• Stop this process once val hits zero.

5.2Decimal $\rightarrow$ Hexadecimal¶

The slidedeck below converts 165 into its hexadecimal representation, 0xA5.

Let val be 165 in the explanation below. Click to show.

We leave it to you to translate the binary conversion process we described colloquially into a hexadecimal conversion process.

5.3Binary $\leftrightarrow$ Hexadecimal Is Straightforward¶

Given the above, consider the following process for converting to binary to hexidecimal, which composes the processes we’ve discussed above:

1. Convert binary to decimal.

2. Convert decimal to hexadecimal.

This process is tedious—computing powers of twos is doable, but does every computer architect memorize powers of sixteen? Instead, we can directly convert between binary and hexadecimal with the observation:

There exists a one-to-one mapping between the set of hexadecimal digits and the set of length-four binary strings.

The above observation implies that a $4k$-length binary string can be translated into a $k$-length hexadecimal string by independently converting each length-4 binary string into a hexadecimal digit, then concatenating the result. (We leave the proof of this to those of you that are enthusiastic mathematicians.) This makes conversion between binary and hexadecimal much easier:

To convert 0x1E to binary:

• 1 in hexadecimal is 0001 in binary

• E in hexadecimal is 1110 in binary

• Concatenate: 0001 1110 (we include the spaces to make visualizing easier)

• Drop leading zeros and compress spaces. (Optional) Add the 0b prefix to denote binary: 0b11110

To convert 0b11110 to hexadecimal:

• First group into full 4-bit strings, left-padding with zeros where necessary: 0001 1110

• 0001 in binary is 1 in hexadecimal

• 1110 in hexadecimal is E in hexadecimal

• Concatenate: 0x1E (we add the 0x prefix to denote hexadecimal)

6The computer knows it, too¶

At this point, it’s worthwhile to remind first-time readers that the two-character prefix 0b and 0x denote that the digits should be interpreted as binary and hexadecimal representations, respectfully. The 0 in 0b and 0x doesn’t mean anything by itself.

These prefixes allow computers to parse strings of digits and interpret them in their intended base.

#include <stdio.h>
int main() {
  const int N = 1234;
  printf("Decimal: %d\n",N);
  printf("Hex: 	  %x\n",N);
  printf("Octal:   %o\n",N);

  printf("Literals (not supported by all compilers):\n");
  printf("0x4d2         = %d (hex)\n", 0x4d2);
  printf("0b10011010010 = %d (binary)\n", 0b10011010010);
  printf("02322         = %d (octal, prefix 0 - zero)\n", 0x4d2);
  return 0;
}

Output:

Decimal: 1234
Hex:     4d2
Octal:   2322
Literals (not supported by all compilers):
0x4d2         = 1234 (hex)
0b10011010010 = 1234 (binary)
02322         = 1234 (octal, prefix 0 - zero)

We don’t expect you to understand this code at this time. We will discuss C syntax, compilers, literals, etc. very soon. We also will not cover octal literals in this course; most standard C compilers will recognize hexadecimal and binary literals.

7Which base do we use?¶

Remember that there is only ever one number that can be represented in multiple ways. These are all the same number, thirty-two:

• 32₁₀, or simply 32. We recommend you write $32_{ten}$ if you’re writing by hand.

• 0x20, or the hexadecimal numeral 20

• 0b10000, or the binary numeral 10000

• 20₁₆. We recommend $32_{hex}$ if you’re writing by hand.

• 10000₂. We recommend $10000_{two}$ if you’re writing by hand.

Different representations serve different purposes:

• Decimal: Great for humans, especially when doing arithmetic. We hope you won’t ever forget base-10 :-)

• Binary: What computers use. To a computer, numbers are stored as binary data, regardless of how numbers are specified.

• Hex: Hopefully you have realized by now that long strings of binary numbers are hard to parse. Hexadecimal is terrible for arithmetic on paper, but it is much more compact than binary while also being much much easier than decimal as a more compact way of representing binary values.

  We use two strategies in this course to more easily visualize strings of 32 bits, 64 bits, etc.:

  • Group 4 bits at a time

  • Convert each group of 4 bits to its hexadecimal digit

Above all, remember that computers operate in binary, but humans don’t. So it’s good to get more comfortable with converting between these representations before we move further.