Front Matter1 set Theory2 Combinatorics3 Logic4 much more on Sets5 arrival to matrix Algebra6 Relations7 Functions8 Recursion and also Recurrence Relations9 Graph Theory10 Trees11 Algebraic Structures12 much more Matrix Algebra13 Boolean Algebra14 Monoids and Automata15 group Theory and Applications16 An introduction to Rings and also FieldsA AlgorithmsB Python and SageMathC Determinants
Authored in PreTeXt
*

Section 1.4 Binary depiction of hopeful Integers

Subsection 1.4.1 grouping by Twos

Recall the the set of optimistic integers, (mathbbP ext,) is (1, 2, 3, . . . \text.) positive integers are naturally used to counting things. There are numerous ways come count and also many ways to record, or represent, the outcomes of counting. Because that example, if we wanted to count five hundred twenty-three apples, we could group the apples by tens. There would be fifty-two groups of ten through three single apples left over. The fifty-two teams of ten can be put into five groups that ten 10s (hundreds), with two tens left over. The five hundreds, 2 tens, and also three devices is recorded as 523. This system of count is dubbed the basic ten positional system, or decimal system. It is quite herbal for united state to execute grouping through tens, hundreds, thousands, (dots) since it is the an approach that all of us use in daily life.

You are watching: Describe the standard algorithm for finding the binary representation of a positive decimal integer

The term positional describes the reality that every digit in the decimal depiction of a number has a significance based on its position. Of course this method that rearranging digits will readjust the number gift described. You may have learned of numeration equipment in i m sorry the place of symbols does not have any kind of significance (e.g., the ancient Egyptian system). Many of these equipment are just curiosities to us now.

The binary number mechanism differs indigenous the decimal number device in the units are grouped through twos, fours, eights, etc. That is, the team sizes room powers that two instead of powers of ten. For example, twenty-three can be grouped into eleven teams of two through one left over. The eleven twos deserve to be group into 5 groups of 4 with one group of two left over. Continuing along the very same lines, we discover that twenty-three can be defined as one sixteen, zero eights, one four, one two, and one one, i beg your pardon is abbreviation (10111_ extrmtwo ext,) or merely (10111) if the context is clear.

Subsection 1.4.2 A counter Algorithm

The procedure that we supplied to determine the binary depiction of (23) have the right to be described in general terms to identify the binary depiction of any type of positive creature (n ext.) A general summary of a procedure such together this one is dubbed an algorithm. Because this is the very first algorithm in the book, us will an initial write it the end using much less formal language than usual, and also then introduce some “algorithmic notation.” If you space unfamiliar through algorithms, we refer you to Section A.1

Start through an empty list of bits.

Assign the variable (k) the value (n ext.)

While (k)"s value is positive, continue performing the complying with three measures until (k) i do not care zero and then stop.

divide (k) by 2, obtaining a quotient (q) (often denoted (k extrm div 2)) and also a remainder (r) (denoted ((k mod 2))).

attach (r) come the left-hand side of the list of bits.

assign the change (k) the value (q ext.)

Example 1.4.1. An example of conversion to binary.

To recognize the binary depiction of 41 we take the adhering to steps:

(displaystyle 41 = 2 imes 20+ 1 quad perform = 1 )

(displaystyle 20 = 2 imes 10+0 quad perform = 01 )

(displaystyle 10 = 2 imes 5 + 0 quad list = 001 )

(displaystyle 5 = ext2 imes 2+ 1 quad perform =1001)

(displaystyle 2 =2 imes 1+ 0 quad list = 01001 )

(displaystyle 1 = ext2 imes 0 ext+1 quad list = 101001)

Therefore, (41=101001_ extrmtwo)


The notation that we will usage to define this algorithm and also all rather is dubbed pseudocode, an informal variation of the instructions the are typically used in many computer system languages. Check out the following summary carefully, to compare it v the informal summary above. Postposition B, which has a general discussion of the materials of the algorithms in this book, must clear up any type of lingering questions. Anything after // room comments.

Algorithm 1.4.2. Binary counter Algorithm.

An algorithm because that determining the binary representation of a optimistic integer.

Input: a optimistic integer n.

Output: the binary representation of n in the form of a list of bits, through units bit last, twos little next come last, etc.

k := n (qquad ) //initialize k

L := (qquad ) //initialize l to an empty list

While k > 0 do

q := k div 2(qquad )//divide k by 2

r:= k mod 2

L: = prepend r to l (qquad ) //add r come the prior of L

k:= q (qquad )//reassign k

Here is a Sage variation of the algorithm through two alterations. The outputs the binary depiction as a string, and it handles all integers, not simply positive ones.


*

Figure 1.4.3. Through permission indigenous Randall Munroe, http://xkcd.com.

Exercises 1.4.3 Exercises

1.

See more: Perrys F I Know I Ve Been Changed Tyler Perry Play, Tyler Perry'S

Find the binary depiction of each of the complying with positive integers through working through the algorithm by hand. Girlfriend can inspect your answer using the sage cabinet above.