sheng/Binary Representation of Numbers

From CDS 130

Jump to: navigation, search

Binary Representation of Numbers


Contents

  1. Objectives
  2. Binary Representation of Number
    1. Positional notation
    2. Base of the number system
    3. Digits and numerals - bits
    4. Counting in binary representation
    5. Notation
    6. Exponent Notation
    7. The Template Method
    8. Decimal with Template
    9. Decimal with Template
    10. Binary with Template
    11. Binary with Template
    12. Binary to Decimal with Template
    13. Decimal to Binary
    14. Decimal to Binary
  3. Other numeral systems
  4. Beyond Numbers
    1. Wheat and Chessboard problem
    2. Bit patterns
  5. Questions

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

Image:decimal_notation.jpg

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. 11110112 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 11110112. 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

  • 20 is "shorthand" for 1
  • 24 is "shorthand" for 2 \cdot 2 \cdot 2 \cdot 2
  • 100 is "shorthand" for 1
  • 104 is "shorthand" for 10 \cdot 10 \cdot 10 \cdot 10

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
103 102 101 100

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
103 102 101 100
1*103 4*102 7*101 2*100

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
103 102 101 100
1*103 4*102 7*101 2*100
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
23 22 21 20

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
23 22 21 20
1*23 1*22 0*21 1*20

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
23 22 21 20
1*23 1*22 0*21 1*20
8 4 0 1

Answer: 8+4+0+1=13

2.13. Decimal to Binary

In this module, three algorithms were given.

  1. An algorithm for figuring out the rules for multiplying and dividing exponents.
  2. An algorithm for interpreting a set of numbers placed side-by-side, e.g., 1492.
  3. An algorithm for converting from decimal to binary.
  4. Now we need an algorithm for converting from decimal to binary.

So here is the puzzle: Given 9, what are the ?'s?

 ?  ?  ?  ?
23 22 21 20
 ?  ?  ?  ?
 ?  ?  ?  ?

Answer: ?+?+?+?=9

2.14. Decimal to Binary

powers of 2

power of 2210292827262524 23 22 21 20
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

[1]

chess board

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.

Image:math_wheat.jpg

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

[2]

  1. Is it true that every number has a binary representation? And if so, is the binary representation of a number unique?
  2. How many patterns can be formed with a single bit?
  3. Is the pattern 0 1 different from the pattern 1 0?
  4. How many patterns can be formed from three bits?
  5. 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?
  6. What else (besides characters and integers) can be represented with bit patterns?
  7. Do some files contain bit patterns that represent things other than characters?
  8. Can the bit patterns that are used to represent characters represent other things in other contexts?
  9. Can 6827 be rewritten in base 10 notation?
  10. 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.
Personal tools