As I've been working on some piece of code lately, I've reached the moment I had to check an integer value if it is a power of 2 (well - textures related question). Just the same time I discovered, that I'll need not only a simple checkup, but a shift value too... The solution occurs to be very simple - a logarithm with a base of 2. So - there's the procedure, I've just finished...


xor eax,eax
dec eax
bsr eax,[SrcValue]
jz @F
btr [SrcValue],eax
bsr eax,[SrcValue]
jz @F
sbb eax,eax


This procedure returns integer result of log2(n) or -1 if passed value equals to 0 or cannot be converted to integer result. Since BSR/BTR instructions have met a quite good improvement on PII+ processors (in contrast to very slow implementation on PPlain and PMMX), it should be the most apropriate method of calculation - so I think...

Any other ideas?

Regards, Mikael
Posted on 2003-04-24 16:47:58 by MikaelC
Checking if a number is a power of 2 can be done very simply in constant time by observing that subtracting one from a number changes the lowest set bit in it. Thus N & (N - 1) is zero if and only if N is a power of two (i.e. has only one bit set).
Posted on 2003-04-26 06:31:40 by Jibz
Yes - a simple checking can be done this way. But it doesn't provide the logarithm result. As I said - the problem is texture related. So - if i have a value that represents the width of a texture, I need not only to check if it is a power of 2, but I need a value wihich will be used in a pixel drawing routine to shift the corresponing coordinates to get the texutre address too... That's why I wrote the procedure.
Posted on 2003-04-26 08:51:23 by MikaelC

mov ecx, [SrcValue]
mov eax, -1

lea edx, [ecx - 1]
test ecx, edx
jnz @F
bsf eax, ecx

Not much point in the size optimisation of xor/dec imho. There should be plenty of memory to go around, and its not like its in a loop which needs small size for cache reasons.

Posted on 2003-04-26 09:52:25 by Mirno
No point in being sloppy if you can do better with 0 additional effort ;)
or eax, -1
Posted on 2003-04-28 05:42:25 by Jan Wassenberg