Fastest way to find a long's MSB?

Phil Pilgrim (PhiPi)

I'm working on a program that requires a very fast log₂ computation. The "exponent" part of the result is the position of the input number's most-significant bit. Here's the code I came up with to find that bit quickly:

CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

VAR

  long  number, exponent

OBJ

  pst   :       "Parallax Serial Terminal"
  rnd   :       "RealRandom"

PUB start | seed, x

  pst.start(9600)
  rnd.start
  seed := rnd.random
  cognew(@msb, @number)
  repeat 100
    number := x := ?seed & ?seed & ?seed
    repeat while number
    pst.bin(x, 32)
    pst.char(" ")
    pst.dec(exponent)
    pst.char(13)    

DAT

msb           mov       result_addr,par
              add       result_addr,#4

main_lp       rdlong    acc,par wz
        if_z  jmp       #main_lp

'-------[ Begin ]--------------------------------------------------------------

              rev       acc,#0
              neg       accx,acc
              and       accx,acc
              test      accx,_0x0000ffff wc
              muxc      exp,#16
              test      accx,_0x00ff00ff wc
              muxc      exp,#8
              test      accx,_0x0f0f0f0f wc
              muxc      exp,#4
              test      accx,_0x33333333 wc
              muxc      exp,#2
              test      accx,_0x55555555 wc
              muxc      exp,#1                  ' 13 instructions.

'-------[ End ]----------------------------------------------------------------
              
              wrlong    exp,result_addr
              wrlong    zero,par
              jmp       #main_lp

exp           long      0
_0x0000ffff   long      $0000_ffff
_0x00ff00ff   long      $00ff_00ff
_0x0f0f0f0f   long      $0f0f_0f0f
_0x33333333   long      $3333_3333
_0x55555555   long      $5555_5555
zero          long      0

acc           res       1
accx          res       1
result_addr   res       1

Is there a faster way?

-Phil

Tracy Allen

Phil,
Do you happen to know how the >| operator does it?

Phil Pilgrim (PhiPi)

Tracy,

No, I don't. I've never examined the pcode interpreter. But I imagine that space took precedence over time for the more obscure operators.

BTW, I've come to realize that the solution to the stated challenge won't meet my objectives anyway. My overall objective is to compute log(x) for x == 1 .. 1023, normalized to 255 for log(1023). The ROM table lookup won't do that without a post-multiply. (It has to do with compressing the dynamic range of the Prop BOE's 10-bit ADC.)

-Phil