二进制搜索程序集 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 #0
STD IZQ
LDD #8
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 它可能需要一些小的语法调整以使其兼容另一个汇编程序。例如，@@ 表示当前进程）

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

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

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

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

BinarySearch 中的所有寄存器都被销毁了。在条目上使用 PUSH 和 PULL 如果您希望它们受到保护，请退出。

如果找到目标，则 BinarySearch 退出并清除进位，mid_point 使用相关指针更新的变量。如果目标不是，则进位设置找到了，mid_point 是 'garbage'.

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

STACKTOP            equ       [=10=]DFF
Vreset              equ       $FFFE

VARS_ORG            equ       00
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

二进制搜索程序集 68HC11

Binary Search Assembly 68HC11

assembly

binary-search

68hc11