Reference no: EM131788972
Data items are stored in computer memory using a binary representation. In particular, positive integers are commonly stored using the base-two representation described in Section 2.2. This means that the base-ten representation of an integer that appears in a program or in a data file must be converted to a base-two representation. One algorithm for carrying out this conversion uses repeated division by 2, with the successive remainders giving the binary digits in the base-two representation from right to left. For example, the base-two representation of 26 is 11010, as the following computation shows. What data type can be used to keep track of these remainders?
Each of these problems involves a collection of related data items: a pile of cards in Problem 1, a set of railroad cars in Problem 2, a collection of function information in Problem 3, and a sequence of remainders in Problem 4. In Problem 1, the basic operations are adding a card to and removing a card from the top of the discard pile. In Problem 2, the basic operations are pushing a car onto the siding and removing the last car previously placed on the siding. In Problem 3, when a function terminates, a return is made to the last function that was interrupted. Function information must therefore be stored in such a way that the last information stored will be the first removed from storage. From the diagram in Problem 4, we note that the bits that comprise the base-two representation of 26 have been generated in reverse order, from right to left, and that the remainders must therefore be stored in some structure so they can later be displayed in the usual left-to-right order.
In each case we need a "last-discarded-first-removed," "last-pushed-onto-first removed," "last-stored-first-removed," "last-generated-first-displayed" container. To illustrate this behavior, we focus on Problem 4. To display the base-two representation of an integer like 26 in the usual left-to-right sequence, we must "stack up" the remainders generated during the repeated division by 2, as illustrated in the diagram
in Problem 4. When the division process terminates, we can retrieve the bits from this stack of remainders in the required "last-in-first-out" order.
Assuming that a stack data type is available, we could use an algorithm like the following to convert from base-ten to base-two and display the result: