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:
2) Working with n=1,2,...,128:
3) With shiftings:
4) 'Magic' function:
5) Using floating point:
6) Using BSR (or BSF):
Two questions:
a) do you know other fast implementations ?
b) can you implement the above functions in asm and bench them ?
Thank you !
JC
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
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