I'm working on a crossword program, and I need a very fast log2 function on numbers of the form 2^n (in other words, the input values are 1, 2, 4, 8, 16,...,2^31).

A search on the net gave me the following functions:

1) Dumbest:


int log2 = -1;
do{++log2;n >>= 1;}while(n);


2) Working with n=1,2,...,128:


((uint)(05637042010L >> ((((n) % 11) - 1) * 3)) & 7)


3) With shiftings:


unsigned char logtab[256];
for(i=0;i<8;i++) logtab[1<<i]=i;

log2=0; if(n&0xffff0000){n>>=16; log2+=16;}
if(n&0xff00) { n>>=8; log2+=8; }
log2+=logtab[n];


4) 'Magic' function:


unsigned char logtab[32]={0,1,2,6,3,11,7,16,4,14,12,21,8,23,17,26,31,5,10,15,13,20,22,25,30,9,19,24,29,18,28,27};

log2=logtab[(n*0x4653adf)>>27]


5) Using floating point:


float a = (float)n;
log2 = ((*(int *)(&a) >> 23) & 0xFF) - 127;


6) Using BSR (or BSF):


bsr eax, n


Two questions:
a) do you know other fast implementations ?
b) can you implement the above functions in asm and bench them ?

Thank you !

JC
Posted on 2003-09-01 13:43:21 by MCoder
Maybe you can optimize this snippet for your needs?
; by Norbert Juffa


table db 0, 0, 0,15, 0, 1,28, 0,16, 0, 0, 0, 2,21,29, 0
db 0, 0,19,17,10, 0,12, 0, 0, 3, 0, 6, 0,22,30, 0
db 14, 0,27, 0, 0, 0,20, 0,18, 9,11, 0, 5, 0, 0,13
db 26, 0, 0, 8, 0, 4, 0,25, 0, 7,24, 0,23, 0,31, 0

;
; emulate bsf instruction
;
; input:
; eax = number to preform a bsf on ( != 0 )
;
; output:
; edx = result of bsf operation
;
; destroys:
; ecx
; eflags
;

MACRO EMBSF5

mov edx,eax ; do not disturb original argument
dec edx ; n-1
xor edx,eax ; n^(n-1), now EDX = 00..01..11

IFDEF FASTMUL
imul edx,7*255*255*255 ; multiply by Harley's magic number
ELSE
mov ecx,edx ; do multiply using shift/add method
shl edx,3
sub edx,ecx
mov ecx,edx
shl edx,8
sub edx,ecx
mov ecx,edx
shl edx,8
sub edx,ecx
mov ecx,edx
shl edx,8
sub edx,ecx
ENDIF

shr edx,26 ; extract bits <31:26>
movzx edx,[table+edx] ; translate into bit count - 1

ENDM
http://www.df.lth.se/~john_e/gems/gem0039.html
Posted on 2003-09-01 14:26:25 by bitRAKE