Integer Representations
Contents
4.4. Integer Representations#
Have you ever thought about why numbers mean what they mean?
Why does
Consider the natural numbers first.
We have “symbols” which represent the elements of the natural numbers:
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
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
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
The decimal representation of number is positional. We know that
that putting two
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- 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
Theorem
Let
where
This formula for
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
or , a bit, representing “off” or “on” of the electrical voltage.Base-8 (octal) is used throughout computing where numbers were represented using
, , or bits, and thus , , or octal digits.Base-16 (hexadecimal) has become popular in computing where computers now represent numbers using
or bits and thus or hex digits.
We will see the relation between these bases in Section 4.4.3.
Binary numbers
Tip
A binary number with
Hexadecimal is the most obscure of the number system because we have letters as numbers (rather than variables representing numbers).
In hexadecimal,
Hexadecimal numbers
Radix representations
Convert the below numbers to decimal numbers.
Radix representations
Radix- numbers in practice#
In practice, we write radix-
“0b” prefix
“0” or “0o” prefix
“0x” prefix
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
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- #
We have seen that radix-
Let
with
Continue by dividing
with
We continue in this way until

Converting to radix-
Convert
Therefore,
Why does this work? Notice that we have
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
Binary to Octal
Similarly, the hexadecimal system represents 4 binary digits at once.
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
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
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
Radix representations
Binary multiplication can be derived from binary addition with a simple observation.
Let
Since
Therefore,
Binary shift
When multiplying a binary number by a power of
Finally, we can consider how to perform binary multiplication.
Let
Let
.For
, if , then is the product .
Binary multiplication
Compute the product of
To make things easier we compute the product of
We can verify this as
4.4.5. Exercises#
Exercise 4.22
Convert the following numbers to decimal.
Solution to Exercise 4.22
28
237
80396
91068941
Exercise 4.23
Convert the following numbers to octal.
Solution to Exercise 4.23
Exercise 4.24
Convert
radix-
representationradix-
representation
For radix-
Solution to Exercise 4.24
Exercise 4.25
Write a Python function convert(n,r)
which returns a string-encoding of the radix-
Assume that
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
Solution to Exercise 4.26