Integer Representations
Contents
4.4. Integer Representations#
Have you ever thought about why numbers mean what they mean? Why does \(496\) mean “four hundred ninety six”? What does that value actually mean? This is not something we often think about because we learn the decimal system of numbers from the very beginning. It is so ingrained in our way of thinking about math. But, there are many ways we could represent and understand numbers.
Consider the natural numbers first. We have “symbols” which represent the elements of the natural numbers: \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, \ldots\). However, these are not the only way to represent the natural numbers. The natural numbers are really only about counting.
We (as a society) could have easily used other symbols to represent the natural numbers. Romans, for example, used roman numerals.
Fig. 4.1 Roman numeral symbols for representing \(1, 2, \ldots, 10\).#
What if we used a series of dots to encode the number of things being counted? This would be a tally number system.
Fig. 4.2 A set of symbols representing \(1, 2, \ldots, 10\) by “tally”.#
4.4.1. Positional Number Systems#
In contrast with the previous two examples of roman numerals and a tally number system, it is much more convenient to use a positional number system.
In the roman numerals, I means \(1\), V means \(5\), X means \(5\), etc. The position of the symbol does not change its value.
The decimal representation of number is positional. We know that that putting two \(1\) symbols together to form \(11\) means something different than II in Roman numerals.
The decimal number system is a positional number system with radix or base 10. The position of a digit in a number represents a multiple of a certain power of 10.
Radix-\(r\) representations#
We can construct a positional number system with any choice of radix. In modtern times, we have settled on a base 10 representation mainly because humans have 10 fingers. Historically, different groups used different bases. The Mayans used base 20 (10 toes and 10 fingers). The Babylonians used base 60. This is why time and angles are measured in groups of 60 seconds, 60 minutes.
Fig. 4.3 The Kaktovik numerals of the Iñupiat aboriginal group is a base-20 number system which also has the symbol for each digit indicating the value it represents.#
Given some radix \(r\), we can construct a number system using \(r\) as the radix or base. This results from the following theorem.
Theorem
Let \(r\) be a positive integer greater than \(1\). Any positive integer \(n\) can be expressed uniquely in the form:
where \(k\) is a non-negative integer, \(a_j\) (\(0 \leq j \leq k\)) belongs to the set \(\{0, 1, \ldots, r-1\}\) and \(a_k \neq 0\).
This formula for \(n\) is called the radix-\(r\) representation of \(n\). To make it clear what the radix is, we can write the radix-\(r\) representation more succinctly as \((a_ka_{k-1}\cdots a_2a_1a_0)_r\) When the radix is \(10\), we often omit writing the radix explicitly.
In the modern technological age, base-2, base-8, and base-16 are important number systems.
Base-2 (binary) is used throughout electronics as the “digital numbers”. Each digit is \(0\) or \(1\), a bit, representing “off” or “on” of the electrical voltage.
Base-8 (octal) is used throughout computing where numbers were represented using \(6\), \(12\), or \(24\) bits, and thus \(2\), \(4\), or \(8\) octal digits.
Base-16 (hexadecimal) has become popular in computing where computers now represent numbers using \(32\) or \(64\) bits and thus \(8\) or \(16\) hex digits.
We will see the relation between these bases in Section 4.4.3.
Binary numbers
Tip
A binary number with \(n\) digits has a value which ranges from \(0\) to \(2^n - 1\).
Hexadecimal is the most obscure of the number system because we have letters as numbers (rather than variables representing numbers). In hexadecimal, \(A = 10\), \(B= 11\), \(C = 12\), \(D = 13\), \(E = 14\), and \(F = 15\).
Hexadecimal numbers
Radix representations
Convert the below numbers to decimal numbers.
\((11001)_2\)
\((1000011001)_2\)
\((7612)_8\)
\((7612)_{16}\)
Radix representations
\(25\)
\(537\)
\(3978\)
\(30226\)
Radix-\(r\) numbers in practice#
In practice, we write radix-\(r\) representations different from the mathematical way of \((23DFEA4)_{16}\)
“0b” prefix
\(\texttt{0b101101} = 45\)
“0” or “0o” prefix
\(\texttt{0o12654} = 5548\)
“0x” prefix
\(\texttt{0x23DFEA4} = 37617316\)
Most programming languages feature native support for many different radix representations. This includes Python. One can define “literal” numbers in different radix representations use the aforementioned prefixes.
You can also convert a decimal number to binary with \(\texttt{bin()}\), to octal with \(\texttt{oct()}\), and to hexadecimal with \(\texttt{hex()}\). Note that these functions return a string representing the number.
a = 0b101101
b = 0o12654
c = 0x23DFEA4
print("a: %d" % a)
print("b: %d" % b)
print("c: %d" % c)
a: 45
b: 5548
c: 37617316
a = 34562
print("bin(a): %s" % bin(a))
print("oct(a): %s" % oct(a))
print("hex(a): %s" % hex(a))
bin(a): 0b1000011100000010
oct(a): 0o103402
hex(a): 0x8702
4.4.2. Converting to radix-\(r\)#
We have seen that radix-\(r\) representations are an expansion of a number using powers of \(r\) as the base. This suggests that converting from decimal to a radix-\(r\) representation can be performed by (repeated) division.
Let \(r\) be some radix and \(n\) be some integer number to convert to radix-\(r\). By Euclidean division we have:
with \(0 \leq a_0 < r\). Notice that \(a_0\) is thus a digit in the radix-\(r\) number system. In fact, \(a_0\) is the first digit (counting from the right) of the radix-\(r\) representation or \(n\).
Continue by dividing \(q_0\) by \(r\):
with \(0 \leq a_1 < r\). Again, \(a_1\) is a digit in the radix-\(r\) number system and \(a_1\) is the second digit of the radix-\(r\) representation of \(n\).
We continue in this way until \(q_k\) is \(0\), using the successive remainders as the digits of the radix-\(r\) representation of \(n\).
Converting to radix-\(16\)
Convert \(93752\) to hexadecimal.
Therefore, \(93752 = (16E38)_{16}\)
Why does this work? Notice that we have \(n - a_0 = q_0r\). Hence, \(r \mid n - a_0\) and \(n \equiv a_0 \bmod r\). This makes sense because we want:
4.4.3. Binary, Octal, Hex Conversion#
Recall that binary, octal, and hexadecimal numbers all have roots in electronics and computing. It should be no surprise that each of these representations have their own merits in computer science. It is therefore very useful to be able to convert between these representations. Doing such a conversion is very easy.
The binary system uses one digit to represent each bit in a computer system. The octal system, with digits \(0\) through \(7\) represents three binary digits at once: \(7 = (111)_2\), \(6 = (110)_2\), etc. Therefore, we can easily convert from binary to octal by grouping binary digits into threes and then converting each group to its corresponding decimal (octal) digit.
Binary to Octal
Similarly, the hexadecimal system represents 4 binary digits at once. \(15 = (1111)_2\), \(14 = (1110)_2\), \(13 = (1101)_2\), etc. We can easily convert binary to binary to hexadecimal by grouping bits into fours and then converting each group to one hexadecimal digit.
Binary to Hexadecimal
4.4.4. Binary Arithmetic#
Arithmetic like addition, multiplication, division, etc. always give the same result regardless of which number system you are using. Whether in binary, hexadecimal, octal, or decimal, the sum of two numbers is still its sum. The only thing that changes is the way we write down the numbers being added and their sum.
Doing addition and subtraction in the binary number system is not so different from doing it in the decimal system. The key is to understand how we add individual digits, just like in “long addition” in the decimal system.
There are three possibilities for adding single bits: both are \(0\), both are \(1\), or one is \(1\) and the other is \(0\).
This last formula shows how there may be a carry from one “column” of the addition to another. Therefore, we actually have four cases for adding 3 bits together: there are zero \(1\)s, there is one \(1\), there are two \(1\)s, there are three \(1\)s.
Using this basic addition of three bits and the ideas of “carrying” digits, we can compute the addition of any two binary numbers.
Binary addition
Compute \((1101)_2 + (110)_2\) in binary.
Radix representations
Binary multiplication can be derived from binary addition with a simple observation. Let \(m = (a_ka_{k-1}\cdots a_2a_1)_2\) and \(n = (b_\ell b_{\ell-1}\cdots b_2 b_1)_2\). Then:
Since \(m\) is itself a binary number each term \(mb_\ell2^\ell\) has a simple computation. First, since \(b_\ell\) is a binary digit, it is either \(0\) or \(1\). If it is \(0\), the product is also \(0\). If it is \(1\) then \(ab_\ell2^\ell = a2^\ell\). Now, notice that:
Therefore, \(m2^\ell\) is just a shift.
Binary shift
When multiplying a binary number by a power of \(2\), the result is simply a shift of digits to the left, with the corresponding number of \(0\) digits added on the right.
Finally, we can consider how to perform binary multiplication. Let \(m = (a_ka_{k-1}\cdots a_2a_1)_2\) and \(n = (b_\ell b_{\ell-1}\cdots b_2 b_1)_2\).
Let \(p = 0\).
For \(i = 0, \ldots, \ell\), if \(b_i = 1\), then \(p = p + (m \cdot 2^i)\)
\(p\) is the product \(m\cdot m\).
Binary multiplication
Compute the product of \((1010)_2\) and \((11001)_2\).
To make things easier we compute the product of \((11001)_2\) and \((1010)_2\). In the latter we have two \(1\) digits corresponding to \(2^3\) and \(2^1\). Hence, the product is:
We can verify this as \((11001)_2 = 25\), \((1010)_2 = 10\), and \(25\cdot10 = 250 = (11111010)_2\).
4.4.5. Exercises#
Exercise 4.22
Convert the following numbers to decimal.
\((11100)_2\)
\((11101101)_2\)
\((235014)_8\)
\((56D9A0D)_{16}\)
Solution to Exercise 4.22
28
237
80396
91068941
Exercise 4.23
Convert the following numbers to octal.
\(174\)
\((11100)_2\)
\((FFDE)_{16}\)
\(262144\)
Solution to Exercise 4.23
\((256)_8\)
\((34)_8)\)
\((177736)_8\)
\((1000000)_8\)
Exercise 4.24
Convert \(12847\) to:
radix-\(6\) representation
radix-\(13\) representation
For radix-\(13\) use the digits \(\{0,\ldots,9,A,B,C\}\).
Solution to Exercise 4.24
\((135251)_6\)
\((5B03)_{13}\)
Exercise 4.25
Write a Python function convert(n,r) which returns a string-encoding of the radix-\(r\) representation of the integer \(n\).
Assume that \(n\) is non-negative and that \(1 < r \leq 10\). Therefore, you do not have to worry about digits like \(A, B, C\), etc.
Solution to Exercise 4.25
def convert(n,r) :
q = n;
ret = "";
while q != 0 :
ret = str(q % r) + ret;
q = q // r
return ret
print(convert(12847,7))
Exercise 4.26
Using “long” binary multiplication, compute the product of \((101011)_2\) and \((1101)_2\).
Solution to Exercise 4.26
\((1000101111)_2\)