An answer:

        CLR R2  ; "low"
        MOV #50., R3  ; "high"
        MOV 100, R4  ; just for speed (you didn't have to do this for the exam)
  LOOP: MOV R2, R0
        ADD R3, R0
        CLR R1
        DIV #2, R0  ; "mid"
        ; address calculation (this can be optimized)
        MOV R0, R1
	ADD R0, R1  ; i.e. R1 <- [R0] * 2
        ADD #500, R1  ; or use CMP R4, 500(R1) instead of next line
        CMP R4, @R1
        BEQ END  ; "mid" already in R0
        BLT TOOLOW
        MOV R0, R3
        INC R3  ; low := mid + 1
        BR CONT
TOOLOW: MOV R2, R3
  CONT: CMP R3, R2
        BGT LOOP
        MOV #-1, R0
   END: HALT

In practice, I would personally optimize the address calculation by, basically, not dividing by two at that point so that it's still in bytes (this is just a coincidence, that the "/2" in taking the arithmetic mean is the same as the conversion between word and byte offsets, but these coincidences happen all the time and in machine-language programming we tend to take advantage of them), but you'd have to zero the low bit with "BIC #1, R0", and then you could use 500(R0) as the address. But I thought this was a bit too tricky to present as my official exam solution here.

The CLR R1 just before the DIV is required because the PDP-11 takes a two-word source for the numerator. You didn't have to do this for the exam. Actually I think it is probably the other way around: I think that R0 is probably the high word and R1 the low word. Although this strikes me as big-endian, it's how the MUL op works, or so I believe (I don't have personal experience with MUL and DIV on a PDP-11 and this issue seems to be ill-documented). Actually it would be easier to use an ASR (arithmetic right-shift).


[exam] [CSC 258 additional problems] [main course page]