Reference Guide

130 Chapter 7
Programming Examples
1. Binary Search for Highest Bit Position
1. Binary Search for Highest Bit Position
The Shift Double and Extract Unsigned instructions are used to
implement a binary search. Bits shifted into general register 0 are
effectively discarded.
.CODE
.EXPORT post
;
; This procedure calculates the highest bit position
; set in the word passed in as the first argument.
; If passed parameter is non-zero, the algorithm
; starts by assuming it is one.
; A binary search for a set bit is then used
; to enhance performance.
;
; The calculated bit position is returned to the caller.
;
.PROC
post
.CALLINFO SAVE_RP
.ENTER
COMB,=,N %r0,%arg0,all_zeros ; No bits set
LDI 31,%ret0 ; assume 2 to the 0 power
;
; if extracted bits non-zero, fall thru to change assumption
; else set up 16 low order bits and keep assumption
;
EXTRU,<> %arg0,15,16,%r0 ; check 16 high order bits
SHD,TR %arg0,%r0,16,%arg0 ; left shift arg0 16 bits
ADDI -16,%ret0,%ret0 ; assume 2 to the 16 power
;
; if extracted bits non-zero, fall thru to change assumption
; else set up 8 low order bits and keep assumption
;
EXTRU,<> %arg0,7,8,%r0 ; check next 8 high order bits
SHD,TR %arg0,%r0,24,%arg0 ; left shift arg0 8 bits
ADDI -8,%ret0,%ret0 ; assume 8 higher power of 2
;
; if extracted bits non-zero, fall thru to change assumption
; else set up 4 low order bits and keep assumption
;
EXTRU,<> %arg0,3,4,%r0 ; check next 4 high order bits
SHD,TR %arg0,%r0,28,%arg0 ; left shift arg0 4 bits
ADDI -4,%ret0,%ret0 ; assume 4 higher power of 2
;
; if extracted bits non-zero, fall thru to change assumption
; else set up 2 low order bits and keep assumption
;
EXTRU,<> %arg0,1,2,%r0 ; check next 2 high order bits
SHD,TR %arg0,%r0,30,%arg0 ; left shift arg0 2 bits
ADDI -2,%ret0,%ret0 ; assume 2 higher power of 2