Completed: / exercises

Number systems

These exercises do not affect the grade.
This supplementary material introduces the basics of the number systems needed in the course, that is, the different ways in which numbers can be represented. Decimal numbers are familiar to everyone from basic school mathematics, but other bases may have only been encountered at university, or not at all. The examples in this material have been made with Python so that they can be easily run in the
interactive interpreter
.
Learning objectives: After going through this material, you will understand what binary and hexadecimal numbers are and know how to convert numbers from one base to another. You will also know why these other bases are needed in this course. In addition, you will know how to experiment with bitwise operations in the Python interpreter.

Choose your base

As stated above, the so-called normal integers that we have used since basic school are decimal numbers. We have learned to interpret decimal numbers at a glance: we can quickly see that 156 is one hundred and fifty-six. However, this number can also be constructed systematically from its individual digits using the base, which in this case is 10. 
>>> 6 * 10 ** 0 + 5 * 10 ** 1 + 1 * 10 ** 2
156
The expression above is a mathematical description of the fact that, in the decimal system, the rightmost digit represents the ones, the next one the tens, the next one the hundreds, and so on. Breaking the number down from right to left is easier because we can start the exponent at zero and increase it by one as we move forward. The number is therefore not considered as a whole, but as a sum constructed from individual digits. For each digit, the digit is multiplied by the base raised to the power i, where i is the position of the digit in the number (counting from the right and starting from zero). The same thing is shown below in Python code, in case code is clearer than a verbal explanation: 
number = "156"
total = 0
for i, digit in enumerate(number[::-1]):         # [::-1] = iterate from right to left
    total += int(digit) * 10 ** i                # increase the total
    
print(total)                                     # prints 156
The numerical value 10 appearing in this code is the base. It also determines which digits are allowed in the number: 0, 1, ..., 9. In other words, the allowed values are 0, 1, ..., base - 1. This systematic way of breaking numbers down is important because humans are not particularly good at visually reading numbers written in other bases - at least not without practice! The base also means that if the digits of a number are shifted to the left, the result is multiplication by the base. Correspondingly, shifting them to the right results in division by the base. This is easy to see if we take a number ending in zero and also add leading zeros: 
>>> number = "00310"
>>> int(number)
310
>>> number = "03100"          # shifted once to the left
>>> int(number)
3100
>>> number = "00031"          # shifted once to the right (from the original)
>>> int(number)
31

Binary numbers

Binary numbers
are central when dealing with computers. This is because a computer operates only with
bits
- that is, zeros and ones. As it happens, a binary number is simply a number with base 2. Therefore, based on the previous explanation, the allowed digits are 0 and 1. The value of a binary number is constructed using the same idea as in the decimal-number decomposition shown above. We simply replace 10 with 2. Let us use 1011 as an example. 
>>> 1 * 2 ** 0 + 1 * 2 ** 1 + 0 * 2 ** 2 + 1 * 2 ** 3
11
In principle, multiplication by zero could be omitted, but to understand the whole process it is better to see how every digit is decomposed. In code, we could do it using exactly the same principle: 
number = "1011"
total = 0
for i, digit in enumerate(number[::-1]):         # [::-1] = iterate from right to left
    total += int(digit) * 2 ** i                 # increase the total (note: 10 has been replaced by 2!)
    
print(total)                                     # prints 11
Because computers typically work with a limited number of bits, each number is represented using a specific number of bits. This determines how many different values can be represented by a binary number. The number of distinct values is simply 2 ** n, where n is the number of bits. Every time one bit is added, the number of values that can be represented doubles. Notice also that because 0 is included, the largest value that can be represented using an N-bit binary number is 2 ** n - 1 (if we are working only with non-negative integers).
When representing binary numbers, we need to know the order of the bits in the representation. In other words, when we have a bit sequence such as 11101, we need to know how it is interpreted:
How should the binary number 11101 be interpreted as a decimal number??
10111 -> 23
11101 -> 29
In the decimal system, we are accustomed to writing the digit corresponding to the highest power of the base on the left. For example, in the number 156, the first digit represents 1 * 10 ** 2. We do not normally interpret the representation in the opposite direction, where the rightmost digit would represent the highest power.
A similar convention is needed when representing a sequence of bits. We need to know which end contains the least significant bit (LSB), corresponding to the smallest power of two, and which end contains the most significant bit (MSB), corresponding to the largest power of two.
Different computer architectures and documentation can use different bit-ordering and bit-numbering conventions. For this course, we define the convention here: from this point onward, when binary numbers are written in the material, the MSB is the leftmost bit and the LSB is the rightmost bit. So we interpret binary numbers in the same direction as decimal numbers.

There are 10 kinds of people...

...those that can read binary and those who can not. Yeah, an old joke, we know. In any case, let us find out in which group you belong! This task is recommended to do with pen and paper, since that helps with getting better understanding of binary numbers. There are some binary numbers below:
1101111
1011011010
0101010
010
Write the numbers as base 10 numbers in the box one below the other.
Warning: You have not logged in. You cannot answer.

Hexadecimal numbers

Humans are accustomed to reading decimal numbers, while computers use binary numbers. However, there is a problem between these two systems: because 10 is not part of the powers-of-two sequence, we cannot directly see from a decimal number how many bits are required to represent it, nor is it easy to convert it into a
binary number
- it also cannot easily be divided into blocks (we cannot directly say which
bits
produce each individual digit). For example, the numbers 255 and 256 appear to be of roughly the same magnitude, but one can be represented using 8 bits while the other requires 9. Another problem concerns comparing binary numbers. A quick question - are these two numbers the same: 1011001101001011 1011001101101011? Binary numbers are naturally very long, and visually parsing them is difficult.
For these reasons, we use
hexadecimal numbers
as a compromise. These numbers use base 16, and the representation is constructed so that the numbers 10...15 are replaced with the letters A...F.
Hexadecimal numbers
Written in hexadecimal, the binary numbers above would be b34b and b36b, making it considerably easier to see that they are two different numbers. It is also easy to see that their difference is 0x20, which in decimal is 2 * 16 ** 1 (32). Even more useful is the fact that one digit in a hexadecimal number corresponds to exactly four bits:
hexadecimal number and the bits corresponding to its digits
From a hexadecimal number, we can more directly see which bits have changed when comparing two values. This makes life considerably easier when performing
bitwise operations
.
Conversion to decimal works in the familiar way, as long as we remember which numerical values the letters represent. 
>>> 11 * 16 ** 3 + 3 * 16 ** 2 + 6 * 16 ** 1 + 11 * 16 ** 0
45931

The curse of the binaries

In this exercise you turn hexadecimal numbers into binary numbers. Below there is a group of base 16 numbers and your task is to magic them into binaries. It is probably easiest to do it one digit at a time if you remember that 0...f is 0000...1111 in binary. Remember also the leading zero bits! Also this exercise is recommended to do with the use of pen and paper.
f3c1
0917
aa51
Write the corresponding binary numbers in the box below.
Warning: You have not logged in. You cannot answer.

Conversions in the other direction

Here we briefly go through how a decimal number is converted into binary and hexadecimal. Let us start by converting from base 10 to base 2. In this method, the bits are produced from right to left, meaning that the least significant bit is obtained first. The method proceeds by repeatedly dividing the number by two. The remainder is added to the binary number, while the quotient continues to the next iteration, where it is again divided by two and the remainder is recorded. We continue until the quotient is 0. Let us use the number 125, in which case the complete process is:
  1. Divide 125 / 2 -> quotient 62, remainder 1 -> binary number is now '1'
  2. Divide 62 / 2 -> quotient 31, remainder 0 -> binary number is now '01'
  3. Divide 31 / 2 -> quotient 15, remainder 1 -> binary number is now '101'
  4. Divide 15 / 2 -> quotient 7, remainder 1 -> binary number is now '1101'
  5. Divide 7 / 2 -> quotient 3, remainder 1 -> binary number is now '11101'
  6. Divide 3 / 2 -> quotient 1, remainder 1 -> binary number is now '111101'
  7. Divide 1 / 2 -> quotient 0, remainder 1 -> binary number is now '1111101'
As a Python loop, and considering only positive integers: 
binary = ""
number = 125
while number > 0:
    number, bit = divmod(number, 2)           # Calculate the quotient and remainder
    binary = str(bit) + binary                # Note: remember to add the new digit to the *beginning* of the number
    
print(binary)
Not surprisingly, the process works in the same way when converting to a hexadecimal number, but the divisor is naturally the base 16. Let us use a slightly larger number, 4451.
  1. Divide 4451 / 16 -> quotient 278, remainder 3 -> hexadecimal number is now '3'
  2. Divide 278 / 16 -> quotient 17, remainder 6 -> hexadecimal number is now '63'
  3. Divide 17 / 16 -> quotient 1, remainder 1 -> hexadecimal number is now '163'
  4. Divide 1 / 16 -> quotient 0, remainder 1 -> hexadecimal number is now '1163'
The corresponding Python loop:
digits = "0123456789ABCDEF"
hexadecimal = ""
number = 4451
while number > 0:
    number, digit = divmod(number, 16)           # Calculate the quotient and remainder
    hexadecimal = digits[digit] + hexadecimal   # Add the corresponding hexadecimal digit to the beginning
    
print(hexadecimal)
The digits string is needed because the value returned by divmod is an integer between 0 and 15. Converting it directly to a string with str only gives the usual decimal representation: values 0...9 become the digits 0...9, but values 10...15 would become the two-character strings "10"..."15". In hexadecimal, these values must instead be represented by the single digits A...F. The expression digits[digit] maps each value from 0 to 15 to its corresponding hexadecimal digit.

Conversion routine

When debugging low-level programs, the values are often represented in hexadecimal or binary. Let's practice converting numbers between binary, decimal, and hexadecimal! Every case has to be converted correctly only once.
Hint: One can complete these exercises with Python, if one desires.

Warning: You have not logged in. You cannot answer.

Conversions in Python

The
Python interpreter
is a convenient tool for working with numbers in different bases. Here we briefly go through how it can be used to convert numbers from one base to another.
Binary numbers
can be written in the Python interpreter by adding 0b to the beginning of the number to indicate that it should be interpreted as a base-2 number:
>>> 0b1011
11
Similarly, in Python you can easily obtain the binary representation of an integer using the bin function:
>>> bin(11)
'0b1011'
Python integers do not store information about the number system in which the number was represented. Binary and hexadecimal numbers can be written in Python code using the 0b and 0x prefixes, but representations produced by functions such as bin and hex are stored as strings.
A binary number can be read from a string using the int function with an additional argument specifying the base of the number contained in the string: 
>>> int("1011", 2)
11
Correspondingly, a
hexadecimal number
can be entered into Python using the 0x prefix:
>>> 0xb36b
45931
Or by using the int function with an additional argument:
>>> int("b36b", 16)
45931
The conversion in the other direction can be done using the hex function:
>>> hex(45931)
'0xb36b'

Finally

That's all for this part, back to the main topic!
?