1

我必须在程序集（69HC11）中使用循环制作二进制搜索算法。这就是我所做的：

    ORG $C400
;n1-n5 will have numbers
N1 RMB 2
N2 RMB 2
N3 RMB 2
N4 RMB 2
N5 RMB 2
IZQ RMB 2
DER RMB 2
;Here is where is going to be the answer
MID RMB 2
;The number im searching
T RMB 2
    ORG $C500
LDD #$400
STD IZQ
LDD #$408
STD DER
LOOP:   LDD IZQ
        ADDD DER
        LDX #2
        IDIV
        STX MID
        LDD MID
        CPD #T
        BLO LAZO1
        BHI LAZO2
        BEQ LAZO3
        LDD IZQ
        CPD DER
        BLS LOOP
LAZO1:
;izq = mid + 1
    INX
    STX IZQ
    BRA LOOP

LAZO2:
;der = mid - 1
    DEX
    STX DER
    BRA LOOP

LAZO3:
Fin:  BRA Fin

问题是我想计算中间位置的循环，然后将位于该位置的值存储在 D 中。我试图写类似 $MID 的东西，但不可行。

4

1 回答 1

0

（首先我使用了这个汇编器：http ://www.aspisys.com/asm11.htm 它可能需要一些小的语法调整以使其与另一个汇编器兼容。例如，@@ 表示当前的本地符号过程）

最好使用简单的索引（0..N-1）而不是实际的内存地址，这取决于字长可能会使计算中点变得更加困难。

为了更简单，您可以使用单字节头和尾变量，但您的最大数组将被限制为 256 个条目。我将其保留为单词，最多提供 64K 条目。

为了简化初始化，我使用了一个静态数组（位于 ROM 中）。如果你想让数组在 RAM 中，你需要先用一些数据初始化它，而不是使用 DW 指令，你应该使用 RMB WORD_SIZE*ARRAY_SIZE 来分配内存区域。

根本不需要使用全局变量。您可以编写 BinarySearch 例程，以便它可以用于不同的表。例如，可以在寄存器 D 中传递目标值，在寄存器 X 中传递数组的起始地址，在寄存器 Y 中传递数组元素的数量。然后，您的工作变量（mid_point、target、head 和 tail）都可以在进入 Search 时在堆栈上动态分配，并在退出前取消分配，同时将结果（mid_point）加载到寄存器 X（例如）。

所有寄存器都在 BinarySearch 中销毁。如果您希望它们受到保护，请在进入时使用 PUSH，在退出时使用 PULL。

如果找到目标，则 BinarySearch 以 Carry Clear 退出，并使用相关指针更新 mid_point 变量。如果未找到目标，则设置进位，并且 mid_point 是“垃圾”。

;*******************************************************************************
; Constants
;*******************************************************************************

STACKTOP            equ       $0DFF
Vreset              equ       $FFFE

VARS_ORG            equ       $0300
ARRAY_ORG           equ       $C400
CODE_ORG            equ       $C500

;*******************************************************************************
; Variables
;*******************************************************************************

                    #RAM
                    org       VARS_ORG

mid_point           rmb       2                   ; eventually holds the answer
target              rmb       2                   ; the number to search for

head                rmb       2                   ; head work pointer
tail                rmb       2                   ; tail work pointer

;*******************************************************************************
; Code
;*******************************************************************************

                    #ROM
                    org       ARRAY_ORG           ;wherever you want your array to be

array               dw        1000
WORD_SIZE           equ       *-array             ;bytes per entry in array
                    dw        2000
                    dw        3000
                    dw        4000
                    dw        5000
                    dw        6000
                    dw        7000
                    dw        8000
                    dw        9000
ARRAY_SIZE          equ       *-array/WORD_SIZE

;*******************************************************************************

                   ;org       CODE_ORG            ;wherever you want your code to be

BinarySearch        proc
                    clra                          ;D = 0
                    clrb
                    std       head                ;initialize head pointer to zero

                    ldd       #ARRAY_SIZE-1       ;initialize tail pointer to N-1
                    std       tail

Loop@@              ldd       head
                    addd      tail
                    rora                          ;LSRD will not work if previous
                    rorb                          ; ADDD produced a carry
                    std       mid_point           ;update mid_point
                    lsld                          ;multiply by WORD_SIZE (x2 -- a shift left will do)
                    addd      #array              ;offset into array
                    xgdx                          ;X = pointer

                    ldd       target              ;target number to search for
                    cpd       ,x                  ;compare against array value
                    beq       Found@@             ;if equal, we're done
                    bhi       Upper@@             ;if greater than, use upper half
;                   blo       Lower@@             ;if less than, use lower half

Lower@@             ldx       mid_point           ;tail = mid_point - 1
                    dex
                    stx       tail
                    bra       Cont@@

Upper@@             ldx       mid_point           ;head = mid_point + 1
                    inx
                    stx       head

Cont@@              ldx       head
                    cpx       tail
                    bls       Loop@@

NotFound@@          sec                           ;indicates 'not found'
                    bra       Done@@

Found@@             ldd       mid_point
                    lsld
                    addd      #array
                    std       mid_point
                    clc                           ;indicates 'found'
Done@@              rts

;*******************************************************************************

Start               proc
                    lds       #STACKTOP

                    ldd       #12345
                    std       target
                    bsr       BinarySearch

                    ldd       #5000
                    std       target
                    bsr       BinarySearch

                    ldd       #3000
                    std       target
                    bsr       BinarySearch

                    bra       *

;*******************************************************************************

                    #VECTORS
                    org       Vreset
                    dw        Start
于 2016-10-31T13:15:58.557 回答