Integer Bases

The number 10 is very important in normal human arithmetic. We have exactly 10 digits - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 - which can appear in any place (ones, tens, hundreds, etc) in a number. And each place is named after a power of 10, starting from the ones place (10⁰), then the tens place (10¹), and so forth. The digit in the ith place tells you exactly how many 10ⁱ are in the number when broken into powers of 10.

Turns out 10 isn't intrinsically special to mathematics. Humans probably chose it only because we have 10 fingers and 10 toes. We can choose any replacement for 10 - which we'll call the base - and write down any number we want using that base as a cornerstone.

For example, the number 52 (5 10s and 3 1s) can be reformed in base 3 as 1 27s, 2 9s, 2 3s, and 1 1s. We write this down as 1221₃, where the 3 marks it as base 3 so that we understand that each digit represents the number of a power of 3, not 10.

Decimal

As mentioned, humans use a base of 10. We give base 10 the special name of "decimal". Note that this is the name for the number system - this applies to integers, not just to fractional values, like the other meaning of "decimal".

Binary

For computers, it's convenient to have as few digits as possible. Elecrical engineers have settled on just 2 digits - 0 and 1 - which in hardware represent a low vs a high voltage. This usage of base 2 is embedded deep inside computer hardware, and when we study computer systems, we see some of its influences.

We give base 2 a special name: "binary". We also often give binary numbers the special prefix of "0b" to distinguish it as a binary number.

Like with the base 3 example above, each place represents the number of a power of two contained in the number. So we have the ones place, the twos place, the fours place, the eights place, and so forth.

For example, take the number 0b100101. What number does it represent? Let's convert it into decimal so our human brains can recognize it more easily. We can convert it by adding up the powers of 2 present in the number - the leftmost 1 represents the 32's place, so we start with 32, then add the 4 from the 1 in the 4's place, then add the 1 from the 1's place. We end up with 37.

Bases are number representations, not new numbers

It may be tempting to consider 0b100101 and 37₁₀ different numbers. After all, they look quite different. However, be careful not to do so. They have the same value - if you have 0b100101 chickens and I have 37₁₀ chickens, we have the same number of chickens. These are simply different ways to write the same number.

Doing conversions is only a way to re-represent the number. The value of the number is not converted, but remains the same.

Decimal-Binary Conversion

We already saw how to convert from binary to decimal - sum up the powers of two present in the number. How about the other way?

We have to do this in reverse. Let's take our 37₁₀ example. To convert to binary, we need to find the largest power of 2 present in the number, remove it, and do so repeatedly. There should be a 1 for each power of 2 we find, and a 0 for the rest.

32 is the largest power of 2 present in 37, and removing that leaves us with 5. There are no 16s or 8s present in 5. However, there is a 4, so we remove that to leave behind 1. There are no 2s present in 1, but there is a 1, so we remove that, and we've hit 0 so we're done.

We saw 1 32, 0 16s, 0 8s, 1 4, 0 2s, and 1 1, so our binary representation is 0b100101, which matches what we saw before.

Binary is Verbose

Binary having fewer digits doesn't come for free. In return, we often need to write down more binary digits to represent a number. We already saw how a 2-digit decimal number like 37 required 6 binary digits to represent it.

To take this further, consider a modest value of a million (1000000₁₀). What's this in binary? 0b11110100001001000000. I don't even want to count how many digits there are.

Hexadecimal

To solve the verbosity problem, computer scientists have adopted another base - base 16. We give it the special name "hexadecimal" or "hex", and often give hexadecimal numbers the special prefix of "0x" to distinguish it as a hex number.

Why 16? Because it's more than 10, it's less verbose than even decimal, and due to mathematical properties we won't discuss, it being a power of 2 means that it's very easy to convert between binary and decimal, making hexadecimal a convenient shorthand for binary.

Note that computers don't use hexadecimal - we just use it as a convenient form of communicating numbers that would be very verbose in binary.

Wait - if the first 10 digits of hex are the same as in decimal, what are the other 6? That is, the digits that represent having 10 of a power of 16, 11 of a power of 16, etc. Well, we borrow letters from the English alphabet. "a" is used for 10, "b" for 11, and so forth up to "f" being used for 15.

So for example, 0x2c means 2 16s and c (12) 1s, which 2x16+12 = 44.

Decimal-Hexadecimal Conversion

You probably won't have to convert between base 10 and 16 often. It's much more common to need to convert between binary and hex.

But if you do, the process is similar to decimal-binary conversion. To convert from hex to decimal, sum up powers of 16 present in the hex number. For example, in 0x21b, we have 2 256s, 1 16, and b (11) 1s = 512 + 16 + 11 = 539.

To convert from decimal to hex, similarly find the largest power of 16 present in the number, and remove as many as possible, then continue on the remainder. For example, for 539, the largest power of 16 is 256, and we can remove 2, leaving behind 27. We can remove a single 16, leaving behind 11, and b (11) 1s. Thus, 2 256s, 1 16, b 1s, so our hex representation is 0x21b.

Binary-Hexadecimal Conversion

The reason why binary-hexadecimal conversion is so convenient is because not only are there exactly 4 times as many binary digits than hex digits for a given value, but every 4 binary digits corresponds to a hex digit. For example, 0x21b in binary is 0b001000011011. We can line them up like this:

0x---2 ---1 ---b

0b0010 0001 1011

0010 corresponds to 2, 0001 corresponds to 1, and 1011 corresponds to b. You'll see that the 4 binary digits are the binary representations of the digit. That's no coincidence.

For your reference:

So to convert from hexadecimal to binary, replace every hex digit with the binary equivalent from this table.

To convert from binary to hexadecimal, add leading 0s until the number of digits is a multiple of 4, then divy up the binary number into groups of 4 bits. Convert each to a hex digit using the table in order.

Using the Computer for Conversions

You should practice enough to feel comfortable converting between any two of decimal, binary, and hexadecimal. But it's not necessary to always do large calculations by hand - gdb can do conversions for you too. You can invoke gdb with gdb -q (the -q flag, which stands for quiet, prevents gdb from printing a lot of text on startup).

The print command, commonly abbreviated p, can print numbers in any of the decimal, binary, or hexadecimal base representations. You can denote which of these to print in by entering the option in your print command.

For example, to print 397 in hex, you would enter p/x 397. Or to print 0xface in binary, you would enter p/t 0xface.

You might ask why binary's option is t and not b. As it turns out, b has a different meaning. Here, the t stands for base Two.

Aside: Integer Literals in C

As you're aware, you can put a decimal number in your C code by just writing it down. For example,

int x = 20;

puts a value of 20 into x.

What if you want to express your integer in hexadecimal? That's fine - use the 0x prefix. The equivalent code would be

int x = 0x14;

What if you want to express your integer in binary? Unfortunately, C doesn't have this built-in. Now, you'll find that if you try a 0b-prefixed number, it'll turn out to work. But that's only because the particular tools we're using (specifically gcc) happen to accept it. It's not valid C, and you should not use 0b-prefixed numbers in your code. Use hexadecimal if you want to express an integer in terms of its bits.