9. array[EDX+ESI] is an example of a base-index-displacement operand. 10. Binary
ID: 3759914 • Letter: 9
Question
9. array[EDX+ESI] is an example of a base-index-displacement operand.
10. Binary search uses a divide and conquer strategy.
11. On the first pass through an array of N items, the inner loop of a bubble sort executes N - 1 times.
12. If an O(n2 ) sorting algorithm requires 0.2 seconds to sort an array of 1,000 elements, it will require 200 seconds to sort 10,000 elements.
13. In 64-bit mode, operands that use register indexes must use 64-bit registers. You can use both base-index operands and base-index-displacement operands.
14. The REPNE prefix repeats an instruction while the Zero flag is set, and ECX is greater than zero.
15. The CLD instruction causes the ESI and EDI registers to be increased in value by the MOVSB instruction.
Explanation / Answer
9)Usually ESI and EDI are used as regular data registers. But when using the string instructions they have special functions.
Indexing: constant base + register.
The effective address is computed by:
Base + (Index * Scale factor) + signed displacement.
The beginning of the array is given by a base register (EAX, EBX, ECX, EDX, ESI, EDI,
EBP, ESP) and a displacement, and the value of the index register (EAX, EBX, ECX,
EDX, ESI, EDI, EBP) selects an element within the array. The scale factor is used to
specify how large the elements in the array are (in bytes). The scale factor can only be 1,
2, 4 or 8. The signed displacement must be either an 8, 16 or 32-bit value.
mov EAX, [EBX+ESI] ; AX = memory[EBX + (ESI * 1) + 0]
mov EAX, [EBX+EPI*4+2] ; AX = memory[EBX + (EPP * 4) + 2
10) D&C algorithm should have two disjoint recursive calls. I.e like QuickSort.
Binary Search does not have this, even if it can be implemented recursively, so i guess this is the answer.
very iteration eliminates half of the remaining possibilities. This makes binary searches very efficient - even for large collections.
Binary search requires a sorted collection. Also, binary searching can only be applied to a collection that allows random access (indexing).
Worst case performance: O(log n)
Best case performance: O(1)
11)The algorithm for bubble sort requires a pair of nested loops. The outer loop must iterate once for each element in the data set (of size n) while the inner loop iterates n times the first time it is entered, n-1 times the second, and so on.
Consider the purpose of each loop.Bubble sort is structured so that on each pass through the list the next largest element of the data is moved to its proper place.
Therefore, to get all n elements in their correct places, the outer loop must be executed n times.
The inner loop is executed on each iteration of the outer loop. Its purpose is to put the next largest element is being put into place.
The inner loop therefore does the comparing and swapping of adjacent elements.
To determine the complexity of this loop, we calculate the number of comparisons that have to be made.
On the first iteration of the outer loop, while trying to place the largest element, there have to be n - 1 comparisons: the first comparison is made between the first and second elements, the second is made between the second and third elements, and so on until the n-1th comparison is made between the n-1th and the nth element.
On the second iteration of the outer loop, there is no need to compare the against the last element of the list, because it was put in the correct place on the previous pass. Therefore, the second iteration requires only n-2 comparisons. This pattern continues until the second-to-last iteration of the outer loop when only the first two elements of the list are unsorted;
clearly in this case, only one comparison is necessary. The total number of comparisons, therefore, is (n - 1) + (n - 2)...(2) + (1) = n(n - 1)/2 or O(n2) .
Best Case: n Average Case:n2 Worst Case:n2
12)True or False
If an O(n 2 ) sorting algorithm requires 0.2 seconds to sort an array of 1,000 elements, it will require 200 seconds to sort 10,000 elements. False
13)Operand(s) is(are) registers EA = R
Register R is EA (not contents of R)
There are a limited number of registers
Therefore a very small address field is needed
Shorter instructions
Faster instruction fetch
X86: 3 bits used to specify one of 8 registers
No memory access needed to fetch EA
Very fast execution
Very limited address space
Multiple registers can help performance
Requires good assembly programming or compiler writing
Note: in C you can specify register variables, register int a;
This is only advisory to the compiler
No guarantees
14)EPNE or REPNZ: It is also conditional repeat. It repeats the operation while the zero flag indicates not equal/zero.
It stops when the ZF indicates equal/zero or when CX is decremented to zero.
The string instructions, by themselves, do not operate on strings of data.
The MOVS instruction, for example, will move a single byte, word, or double word. When executed by itself, the MOVS instruction ignores the value in the ECX register.
The repeat prefixes tell the 80x86 to do a multi-byte string
The syntax for the repeat prefix is:
repne.scasb(); // Note: repnz is a synonym for repne.
repne.scasw();
repne.scasd();
You don't normally use the repeat prefixes with the LODS instruction.
When specifying the repeat prefix before a string instruction, the string instruction repeats ECX times2.
Without the repeat prefix, the instruction operates only on a single byte, word, or double word.
You can use repeat prefixes to process entire strings with a single instruction.
You can use the string instructions, without the repeat prefix, as string primitive operations to synthesize more powerful string operations.
15)(1) Source elements are DS:SI
(2) Destination elements are ES:DI
(3) At the end of the string instruction, the DI and SI are automatically updated by 1 (byte) or 2 (word).
(4) The DF flag is used to determine increment or decrement. If DF=0 then increment; otherwise, decrement.
(5) In Protected Mode, ESI is an offset from DS and EDI is an offset from ES and ES & DS are set to point to the same segment. In Real Mode, ES and DS do not necessarily point to the same location.
(i62) [<label>] CLD
(i63) [<label>] STD
The MOVSB instruction causes the microprocessor to replace the byte at ES:DI by the byte at DS:SI and update DI and SI to point to the next byte in the strings pointed to by DI and SI. The general form is:
(i64) [<label>] MOVSB
A similar instruction exists for moving words as follows:
(i65) [<label>] MOVSW
The two load instructions cause AL and AX-registers to be loaded with a copy of the byte and word addressed by the DS:SI. Notice that these two instructions work with the SI, i.e. we are loading from a source. Also, the SI register is automatically updated as with all string instructions so I will quit mentioning this from now on.
(i66) [<label>] LODSB ; al <- ds:si
(i67) [<label>] LODSW ; ax <- ds:si
The two store instructions cause AL and AX-registers to be stored in the byte and word addressed by the ES:DI. Notice that these two instructions work with the DI, i.e. we are storing to a destination.
(i68) [<label>] STOSB ; al -> es:di
(i69) [<label>] STOSW ; ax -> es:di
Compare and scan string instructions are as follows:
(i70) [<label>] CMPSB ; ds:si - es:di
(i71) [<label>] CMPSW ; ds:si - es:di
(i72) [<label>] SCASB ; al - es:di
(i73) [<label>] SCASW ; ax - es:di
If you are reading the book you will notice that there are generic forms of these string instructions and I don't even want to discuss this.
If you would like to read up on these and use them at any point, feel free. You will not be tested on these instructions.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.