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};

``````

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