sheng/Binary Representation of Numbers
From CDS 130
Binary Representation of Numbers
1. Objectives
- Unary numeral system
- Positional numeral system
- Different bases used in numbering
- Interpretation of the base
- Representation of numbers with different bases
- Powers of two
- Introduce binary numbers
2. Binary Representation of Number
2.1. Positional notation
2.2. Base of the number system
- Definition: In mathematical numeral systems, the base or radix is usually the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is 10, because it uses the 10 digits from 0 through 9.
- interpretation of base-2
2.3. Digits and numerals - bits
- In order to discuss bases other than the decimal system (base ten), a distinction needs to be made between a number and the digit representing that number. Each digit may be represented by a unique symbol or by a limited set of symbols.
- Binary digits (bits) 0 and 1
2.4. Counting in binary representation
0000, 0001, (rightmost digit starts over, and next digit is incremented) 0010, 0011, (rightmost two digits start over, and next digit is incremented) 0100, 0101, 0110, 0111, (rightmost three digits start over, and the next digit is incremented) 1000, 1001, ...
2.5. Notation
- A common way of expressing the base is writing it as a decimal subscript after the number that is being represented. 1111011_{2} implies that the number 1111011 is a base 2 number. When using the written abbreviations of number bases, the base is not printed: Binary 1111011 is the same as 1111011_{2}. The base b may also be indicated by the phrase "base b". So binary numbers are "base 2"; octal numbers are "base 8"; decimal numbers are "base 10"; and so on.
2.6. Exponent Notation
- 2^{0} is "shorthand" for 1
- 2^{4} is "shorthand" for
- 10^{0} is "shorthand" for 1
- 10^{4} is "shorthand" for
2.7. The Template Method
- Before trying to convert binary numbers to decimal numbers, break the process of how we interpret a list of numbers from 0-9 into four steps.
- We call this the template method.
- (Most of the time you don't even notice that you are doing these steps.)
Steps 1 and 2
Create a table with the number and the powers of 10 below it like this:
1 | 4 | 7 | 2 |
---|---|---|---|
10^{3} | 10^{2} | 10^{1} | 10^{0} |
2.8. Decimal with Template
Step 3
Multiply the values in the first row with the values below it in the second row. Place the values in the third row.
1 | 4 | 7 | 2 |
---|---|---|---|
10^{3} | 10^{2} | 10^{1} | 10^{0} |
1*10^{3} | 4*10^{2} | 7*10^{1} | 2*10^{0} |
2.9. Decimal with Template
Step 4
Do the math in row 3 and put values in row 4. Add all values in row 4 to get answer.
1 | 4 | 7 | 2 |
---|---|---|---|
10^{3} | 10^{2} | 10^{1} | 10^{0} |
1*10^{3} | 4*10^{2} | 7*10^{1} | 2*10^{0} |
1000 | 400 | 70 | 2 |
Answer = 1000+400+70+2 = 1472
2.10. Binary with Template
Steps 1 and 2
Create a table with your number and the powers of 2:
1 | 1 | 0 | 1 |
---|---|---|---|
2^{3} | 2^{2} | 2^{1} | 2^{0} |
2.11. Binary with Template
Step 3
Multiply the values in the first row with the values below it in the second row. Place the values in the third row.
1 | 1 | 0 | 1 |
---|---|---|---|
2^{3} | 2^{2} | 2^{1} | 2^{0} |
1*2^{3} | 1*2^{2} | 0*2^{1} | 1*2^{0} |
2.12. Binary to Decimal with Template
Step 4
Do the math in row 3 and put values in row 4. Add all values in row 4 to get answer.
1 | 1 | 0 | 1 |
---|---|---|---|
2^{3} | 2^{2} | 2^{1} | 2^{0} |
1*2^{3} | 1*2^{2} | 0*2^{1} | 1*2^{0} |
8 | 4 | 0 | 1 |
Answer: 8+4+0+1=13
2.13. Decimal to Binary
In this module, three algorithms were given.
- An algorithm for figuring out the rules for multiplying and dividing exponents.
- An algorithm for interpreting a set of numbers placed side-by-side, e.g., 1492.
- An algorithm for converting from decimal to binary.
- Now we need an algorithm for converting from decimal to binary.
So here is the puzzle: Given 9, what are the ?'s?
? | ? | ? | ? |
---|---|---|---|
2^{3} | 2^{2} | 2^{1} | 2^{0} |
? | ? | ? | ? |
? | ? | ? | ? |
Answer: ?+?+?+?=9
2.14. Decimal to Binary
powers of 2
power of 2 | 2^{10} | 2^{9} | 2^{8} | 2^{7} | 2^{6} | 2^{5} | 2^{4} | 2^{3} | 2^{2} | 2^{1} | 2^{0} |
Decimal | 1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Include |
3. Other numeral systems
- Decimal base
- Octal base
- Hexadecimal base
4. Beyond Numbers
4.1. Wheat and Chessboard problem
When the creator of the game of chess (in some tellings an ancient Indian mathematician, in others a legendary dravida vellalar named Sessa or Sissa) showed his invention to the ruler of the country, the ruler was so pleased that he gave the inventor the right to name his prize for the invention. The man, who was very wise, asked the king this: that for the first square of the chess board, he would receive one grain of wheat (in some tellings, rice), two for the second one, four on the third one, and so forth, doubling the amount each time. The ruler, arithmetically unaware, quickly accepted the inventor's offer, even getting offended by his perceived notion that the inventor was asking for such a low price, and ordered the treasurer to count and hand over the wheat to the inventor. However, when the treasurer took more than a week to calculate the amount of wheat, the ruler asked him for a reason for his tardiness. The treasurer then gave him the result of the calculation, and explained that it would be impossible to give the inventor the reward. The ruler then, to get back at the inventor who tried to outsmart him, told the inventor that in order for him to receive his reward, he was to count every single grain that was given to him, in order to make sure that the ruler was not stealing from him.
This equals 18,446,744,073,709,551,615.
4.2. Bit patterns
- What is a bit pattern
- How many bit patterns can be formed by two bits?
- Representing characters with bit patterns
5. Questions
- Is it true that every number has a binary representation? And if so, is the binary representation of a number unique?
- How many patterns can be formed with a single bit?
- Is the pattern 0 1 different from the pattern 1 0?
- How many patterns can be formed from three bits?
- In the past, some computers used 16 bits to form memory addresses. Assuming no special tricks (which such limited machines often used), how many bytes maximum could be held in main storage?
- What else (besides characters and integers) can be represented with bit patterns?
- Do some files contain bit patterns that represent things other than characters?
- Can the bit patterns that are used to represent characters represent other things in other contexts?
- Can 682_{7} be rewritten in base 10 notation?
- An apple vendor has 1000 apples and 10 empty boxes. He asks his son to place all the 1000 apples in all the 10 boxes in such a manner that if he asks for any number of apples from 1 to 1000, his son should be able to pick them in terms of boxes. How did the son place all the apples among the 10 boxes, given that any number of apples can be put in one box.