二进制查找汇编68HC11

Question

我必须使一个二进制搜索算法汇编(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的东西，但是不可能。

Answer 1

(首先我使用了这个汇编器:http://www.aspisys.com/asm11.htm它可能需要一些小的语法调整以使其兼容另一个汇编程序。例如，@@表示局部符号当前的PROC。)

最好使用简单的索引(0..N-1)而不是实际索引内存地址，这取决于字的大小可能使它更多难以计算中点

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

为了简化初始化，我使用了一个静态数组(驻留在ROM中)。如果您希望数组在RAM中，则需要首先使用而不是使用DW指令，您应该使用RMB WORD_SIZE*ARRAY_SIZE用于分配内存区域

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

在BinarySearch中销毁所有寄存器。使用推入和拉入

BinarySearch退出，如果找到目标，则携带清除，并且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