Binary and Hexadecimal

This page explains binary and hexadecimal, the number systems most commonly used in computing.

<Note>
This page uses MathJax to display formulas. If your browser settings block script execution, the formulas on this page will not display correctly.

Decimal and positional notation

How do we normally count? Most people probably count 0, 1, 2, 3, …, 9, 10, 11, …. This representation of numbers is the so-called decimal system.
In decimal, you carry over one place after counting ten (this 10 is called the base or radix), but mathematically there is no particular reason the base has to be 10 (if practicality doesn’t matter, the base could even be a fraction, and as an extreme example one could conceive of base \(\ \pi\ \)). The decimal system is said to be widespread because humans have a total of ten fingers on both hands.
In general, a way of counting in which you carry over after counting \(\ n\ \) is called base \(\ n\ \).

In base \(\ n\ \), numbers are written using \(\ n\ \) distinct symbols called digits. In the decimal system we use every day, we can write numbers using the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Arranging several of these digits lets us represent any number. In base \(\ n\ \), including decimal, the following rules always hold.

Theorem
A base-\(\ n\ \) positional representation always satisfies the following conditions.

1. Each time a number is multiplied by \(\ n\ \), it gains one digit.
2. The numbers that can be represented with a single digit go up to \(\ n-1\ \), and (if Arabic numerals are used) the numeral \(\ 10\ \) represents \(\ n\ \).

In a base-\(\ n\ \) number, the lowest digit is called the ones place. Moving to the left from there, we have the \(\ n\ \)s place, the \(\ n^2\ \)s place, and so on. For \(\ n=10\ \), these are the tens place, the hundreds place, and so on. The number represented by any base-\(\ n\ \) numeral can be expressed in decimal as follows.

Theorem
The number represented by any base-\(\ n\ \) numeral can be written in decimal as \( \sum a_in^i\ \).
Here, \(\ a_i\ \) is the digit in the \(\ n^i\ \)s place.

Binary and hexadecimal

Computers normally use binary as their internal representation of numbers.
Following the definition in the previous section, binary is a positional notation that uses only 0 and 1, in which a number gains one digit each time it is doubled.
However, binary numbers are too long (for humans) to read and write conveniently as they are, so the somewhat more compact hexadecimal system is often used. Following the definition in the previous section, hexadecimal is a positional notation that uses 16 digits, in which a number gains one digit each time it is multiplied by 16. Hexadecimal uses 16 “digits”: the ordinary digits (0-9) plus the six letters A-F.

At this point (and this is not specific to binary or hexadecimal), if you just write the digits as they are, it becomes unclear which base is being used. To avoid such confusion, binary and hexadecimal numbers are marked with special symbols to distinguish them. Unless it is clear from context, a number without any symbol is taken to be decimal.

Notation rules
Unless it is clear from context that a number is binary, a number written in binary is marked explicitly with either the prefix “0b” or “%”.
Unless it is clear from context that a number is hexadecimal, a number written in hexadecimal is marked explicitly with either the prefix “0x” or “\(\$\)”, or the suffix “h”.

In hacking, you will mainly use hexadecimal, but the prefixes are sometimes used for different purposes. The hexadecimal prefix “0x” is often used for general numeric values. The hexadecimal prefix “\(\$\)” is used to indicate data addresses, for example in assembly source code. However, in assembly, hexadecimal literals (constants) use the prefix “\(\#\$\)”, and “0x” is not used.
Incidentally, to convert a binary integer to a hexadecimal integer, you can simply split it into groups of four digits starting from the ones place and map each group to one hexadecimal digit.

Bits, bytes and amount of information

A single binary digit, that is, a digit represented by 0 or 1, is called a bit. A bit is the smallest unit of information. Normally, 0 corresponds to a low-voltage state (low) and 1 corresponds to a high-voltage state (high). Eight bits, that is, eight binary digits, are called a byte, and computers generally handle data in units that are integer multiples of a byte. The SNES CPU, the 65C816, is a 16-bit CPU and can handle 1 or 2 bytes of data at once. The CPUs used in modern PCs are 32-bit or 64-bit CPUs and can handle data in units of 4 or 8 bytes at once.

One byte is 8 bits. Therefore, one byte can represent \(\ 2^8=256\ \) different pieces of information. Similarly, two bytes can represent \(\ 2^{16}=65536\ \), and so on.
Since any data is, from the computer’s point of view, just a number, this is the same as simply saying that one byte can represent the integers 0-255, two bytes the integers 0-65535, and so on. More complex data needs more information, so you can see that it consumes more bytes.

Incidentally, as this fact and the pigeonhole principle show, when considering lossless compression of arbitrary data, no matter what compression algorithm you build, there will always exist data that cannot be compressed at all. A proof is given below.
However, this does not necessarily apply to lossy compression, because the input and output do not have to correspond one-to-one (in fact, it is lossy precisely because they do not).

Proof
The total number of possible pieces of data represented with \(\ n\ \) bits of information is \(\ 2^n\ \).
Compressing this data means obtaining an output at least 1 bit smaller than the original input. Therefore, the output has an amount of information between 1 bit and \(\ n-1\ \) bits (with 0 bits the information would be lost, so it would not count as compression).
The total number of pieces of data represented with at least 1 bit and at most \(\ n-1\ \) bits of information is \(\ \sum_{k=1}^{n-1} 2^k=2^n-2\ \).
This is 2 fewer than the total number of pieces of data that can be represented with \(\ n\ \) bits of information.
Since the compression algorithm under consideration is lossless, the input and output must correspond one-to-one.
Therefore, not all \(\ n\ \)-bit data can be mapped to data of \(\ n-1\ \) bits or less.
Hence, no matter what lossless compression algorithm you make, there exists at least one piece of data that cannot be compressed at all.

Signed number representations

The definition of base-\(\ n\ \) numbers given in the first section of this page applies to non-negative integers, that is, integers greater than or equal to 0. As for how to represent negative numbers, the simplest approach is to attach a minus sign “\( - \)”, just as with the numbers we use every day. However, that kind of representation is not commonly used in the computer world.
Here, we explain four ways of representing negative numbers used in the computer world.

The first is the simplest representation, sign-magnitude representation.

Definition (sign-magnitude representation)
A sign bit is added at the top of a non-negative binary integer; if it is 0 the number is positive, and if it is 1 it represents the negative number with the same absolute value.

All this says is that a 0/1 is put at the front instead of a minus sign. It is exactly the same as the way we normally represent negative numbers, so it is very easy to understand, but it has the drawback of being inefficient for internal computation, and it is rarely used.

The second is a method called excess-N (biased) representation.

Definition (excess-N (biased) representation)
A non-negative integer obtained by adding an arbitrary predetermined integer N to the original value is called the excess-N representation, or biased representation.

This is hard to grasp from words alone, but it is a representation in which the binary values 0 to \(\ N\ \) correspond to \(\ -N\ \) to 0. You can think of it as shifting the number line to the right by \(\ N\ \). This is also not very efficient for internal computation, but because you can choose the range of negative numbers freely, it is occasionally used.
In the SDK series, sprite placement coordinates are represented in excess-256 representation. Also, in the IEEE floating-point standard, the exponent of a single-precision floating-point number is standardized as an 8-bit excess-127 representation, and the exponent of a double-precision floating-point number as an 11-bit excess-1023 representation.

The third is a method called ones’ complement.

Definition (ones’ complement)
One bit is added at the top of a non-negative binary integer, and the value obtained by inverting each bit of this non-negative integer is taken as the negative number with the same absolute value.

The operation of finding this ones’ complement is generally called bit inversion. It was relatively common on old computers, but because internal computation is still somewhat inefficient, it is now a thing of the past. One advantage of this method, however, is that sign inversion can be performed very efficiently. Like sign-magnitude representation, it has the drawback that there are two representations of 0.

The fourth is called two’s complement, and it is used almost exclusively today as the standard signed number representation.

Definition (two’s complement)
The value obtained by adding 1 to the ones’ complement of a non-negative binary integer (the two’s complement) is taken as the negative number with the same absolute value.

Two’s complement representation is widespread today as the standard method, and the SNES CPU, the 65C816, also interprets numbers in two’s complement.
Sign inversion in two’s complement is done by first inverting the bits to obtain the ones’ complement and then adding 1. This is the same whether you are finding a negative number from a positive one or the reverse.
The greatest advantage of two’s complement is that calculations between numbers of different signs, or between negative numbers, can be performed correctly in exactly the same way as calculations between positive numbers. This was not possible with the other three representations, and this ability to make internal computation efficient is the reason two’s complement is widely used today.
For how to represent fractions with integers, see fixed-point numbers.

Binary/hexadecimal conversion table

This table summarizes the binary, decimal and hexadecimal correspondence for simple and important values.

Unsigned integers

Signed 8-bit integers

Signed 16-bit integers