Is there a faster way to find the highest bit set in a 32 bit integer? [Includes C code listing]

[Dann Corbit]

/***********************************************/
/* Locate the position of the highest bit set. */
/* A binary search is used. The result is an */
/* approximation of log2(n) [the integer part] */
/***********************************************/
int ilog2(unsigned long n)
{
int i = (-1);

/* Is there a bit on in the high word? */
/* Else, all the high bits are already zero. */
if (n & 0xffff0000) {
i += 16; /* Update our search position */
n >>= 16; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the high byte of the current word? */
/* Else, all the high bits are already zero. */
if (n & 0xff00) {
i += 8; /* Update our search position */
n >>= 8; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the current nybble? */
/* Else, all the high bits are already zero. */
if (n & 0xf0) {
i += 4; /* Update our search position */
n >>= 4; /* Shift out lower (irrelevant) bits */
}
/* Is there a bit on in the high 2 bits of the current nybble? */
/* 0xc is 1100 in binary... */
/* Else, all the high bits are already zero. */
if (n & 0xc) {
i += 2; /* Update our search position */
n >>= 2; /* Shift out lower (irrelevant) bits */
}
/* Is the 2nd bit on? [ 0x2 is 0010 in binary...] */
/* Else, all the 2nd bit is already zero. */
if (n & 0x2) {
i++; /* Update our search position */
n >>= 1; /* Shift out lower (irrelevant) bit */
}
/* Is the lowest bit set? */
if (n)
i++; /* Update our search position */
return i;
}

--
I don't speak for anybody but myself, which everyone else is thankful for
( -- sig shamelessly purloined from Scott Johnson -- )

[bou...@$smtpg.compsys.com$]

"Dann Corbit" <dco...@solutionsiq.com> wrote:
<snip>
hey Dann:
you could modify your routine something like this (although i would tend to
put this type of routine in assembler)...

int ilg2(unsigned long n)
{
register int i = (n & 0xffff0000) ? 16 : 0;
if( (n >>= i) & 0xff00 ) i |= 8, n >>= 8;
if( n & 0xf0 ) i |= 4, n >>= 4;
if( n & 0xc ) i |= 2, n >>= 2;
return (i | (n>>1));
}

it works (a '1' in the D0 position returns 0, a '1' in the sign position
[i.e. D31] returns 31), it compiles to about 4 instructions per line of
source, and it has a relatively constant running time (like yours <G>)
-- of course it's not very portable without 32bit longs... ;-) i'm also
not sure if it's actually any *faster* than the following:

int ilg2(unsigned long n)
{ register int i = -1; while( n ) ++i, n >>= 1; return i; }

which doesn't depend on the *size* of a long, or even this:

int ilg2(unsigned long n)
{ register int i = 31; if( n == 0 ) return -1;
while( ~n & 0x80000000 ) --i, n <<= 1; return i;
}

which does, but has the advantage of early departure on large #s.

don't forget to decide if what you really want is the largest powerof2 that
contains the entire original number -- you'd need to check lower bits with
mask == ((1 << ilg2(n)) - 1) and add 1 to any of these routines' return
values if any lower bits were non-zero; bit me once...

cheers,
ktb

if you can change the orientation of bits for your application you may find
the following algorithm useful (returns the least-significant bit set)...

inline unsigned lsb(unsigned n)
{ return n & (unsigned) -n; }

btw: if u find an algo which returns the MSB in a simple operation like the
LSB routine above -- plz let me know!! (i've never found one... :-( )

[Stephen Platt]

If you don't mind lookup tables and a setup proc,
(just off the top of my head..)

int lookup[256];

// whateverproc is any scheme to look up the highest bit...
for(i=0; i<256; i++) lookup[i] = whateverproc(i);

int highbitset(int i) {
return i>256 ? lookup[i>>8]+8 : lookup[i];
}

--
----------------------------------------
Stephen M. Platt, Ph. D.
Research and Development
National Software Testing Laboratories
A Division of the McGraw-Hill Companies

[Stephen Westin]

In article <01bc3fac$69b314c0$ca61...@DCorbit.solutionsiq.com> "Dann Corbit" <dco...@solutionsiq.com> writes:

> /***********************************************/
> /* Locate the position of the highest bit set. */
> /* A binary search is used. The result is an */
> /* approximation of log2(n) [the integer part] */
> /***********************************************/
> int ilog2(unsigned long n)
> {

int table[16] = { 0, 1, 2, 2,
3, 3, 3, 3,
4, 4, 4, 4,
4, 4, 4, 4 };

> int i = (-1);
>
> /* Is there a bit on in the high word? */
> /* Else, all the high bits are already zero. */
> if (n & 0xffff0000) {
> i += 16; /* Update our search position */
> n >>= 16; /* Shift out lower (irrelevant) bits */
> }

> /* Is there a bit on in the high byte of the current word? */
> /* Else, all the high bits are already zero. */
> if (n & 0xff00) {
> i += 8; /* Update our search position */
> n >>= 8; /* Shift out lower (irrelevant) bits */
> }
> /* Is there a bit on in the current nybble? */
> /* Else, all the high bits are already zero. */
> if (n & 0xf0) {
> i += 4; /* Update our search position */
> n >>= 4; /* Shift out lower (irrelevant) bits */
> }

i+= table[n];

> return i;
> }

The table could be 256 elements long (for 8 bits), or 65536 (for 16
bits); the idea is to avoid conditional branches, which tend to slow
down modern pipelined machines. The multiplication and address
calculation for the table lookup will probably be faster. In the
extreme, you would use a 16GB table, and reduce the computation to
O(1). But RAM still has to get a bit cheaper for that to be
worthwhile.

--
-Stephen H. Westin
swe...@ford.com
The information and opinions in this message are mine, not Ford's.

[Slaine]

Hi,

Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan reverse)

mov eax, 84h
bsr ebx, eax ;gives ebx =7

...a bit of inline should suffice

These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71) and
not pairable. Compared to code tho.......

Cheers
Slaine

[M. Prasad]

What hardware? It might be faster to do four
table lookups, depending upon your instruction set.

I.e.,
check Ftable[index=first-8-bits].
if non-zero, you have found the first one. (Add 24.)
else check Ftable[index=second-8-bits.]
if non-zero, you have found the first one. (Add 16.)
else check Ftable[index=third-8-bits.]
...

Ftable has 256 entries. Each entry contains a
number between 1 and 8, except the entry
at 0, which contains 0.

Of course, this is best if your instruction set
has a fast table-lookup instruction.

Dann Corbit wrote:
>
> /***********************************************/
> /* Locate the position of the highest bit set. */
> /* A binary search is used. The result is an */
> /* approximation of log2(n) [the integer part] */
> /***********************************************/
> int ilog2(unsigned long n)
> {

> int i = (-1);
>
> /* Is there a bit on in the high word? */
> /* Else, all the high bits are already zero. */
> if (n & 0xffff0000) {
> i += 16; /* Update our search position */
> n >>= 16; /* Shift out lower (irrelevant) bits */
> }
> /* Is there a bit on in the high byte of the current word? */
> /* Else, all the high bits are already zero. */
> if (n & 0xff00) {
> i += 8; /* Update our search position */
> n >>= 8; /* Shift out lower (irrelevant) bits */
> }
> /* Is there a bit on in the current nybble? */
> /* Else, all the high bits are already zero. */
> if (n & 0xf0) {
> i += 4; /* Update our search position */
> n >>= 4; /* Shift out lower (irrelevant) bits */
> }

> /* Is there a bit on in the high 2 bits of the current nybble? */

> /* 0xc is 1100 in binary... */

> /* Else, all the high bits are already zero. */

[Eric Bloodworth]

M. Prasad wrote:
>
> What hardware? It might be faster to do four
> table lookups, depending upon your instruction set.
>
> I.e.,
> check Ftable[index=first-8-bits].
> if non-zero, you have found the first one. (Add 24.)
> else check Ftable[index=second-8-bits.]
> if non-zero, you have found the first one. (Add 16.)
> else check Ftable[index=third-8-bits.]
> ...
>
> Ftable has 256 entries. Each entry contains a
> number between 1 and 8, except the entry
> at 0, which contains 0.
>
> Of course, this is best if your instruction set
> has a fast table-lookup instruction.
>

You could avoid branching by forming a 4 bit index with a
"1" whereever a nonzero byte occurs, looking up an
appropriate shift. Here is the 2 byte case, extend
as necessary to either 4 bytes or 2 16 bit words:

int shift_table[] = { 0, 0, 8, 8 };
index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));
shift = shift_table[index];
bit = shift + Ftable[(val >> shift ) & 0xff];

This is off the top of my head, so I don't know if this
would really help (or work). The penalty for the second
table lookup might wipe out any gains from eliminating the
branching. You'd have to experiment.

--
Eric

[Stephen Westin]

Which MIPS processor are you talking about? They have different
pipelining schemes, which give different instruction timings.

[Slaine]

> > Hi,
> >
> > Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan reverse)
> >
> > mov eax, 84h
> > bsr ebx, eax ;gives ebx =7
> >
> > ...a bit of inline should suffice
> >
> > These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71)
and
> > not pairable. Compared to code tho.......
>
> Which MIPS processor are you talking about? They have different
> pipelining schemes, which give different instruction timings.

MIPS ?? I was unaware that the original poster requested MIPS code.

But, for the record, I am referring to Pentium 32 bit reg to 32 bit reg.

Cheers
Slaine

[Stephen Westin]

In article <334427...@rrinc.com> Eric Bloodworth <er...@rrinc.com> writes:

<snip>

> You could avoid branching by forming a 4 bit index with a
> "1" whereever a nonzero byte occurs, looking up an
> appropriate shift. Here is the 2 byte case, extend
> as necessary to either 4 bytes or 2 16 bit words:
>
> int shift_table[] = { 0, 0, 8, 8 };
> index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));

^ That's a conditional; it's
actually a branch.

> shift = shift_table[index];
> bit = shift + Ftable[(val >> shift ) & 0xff];

But you *did* cut down to one branch...

<snip>

[Stephen Westin]

In article <01bc4094$e5d043a0$5a43...@prs6id9y.prestel.co.uk> "Slaine" <sla...@eternal.prestel.co.uk> writes:

<snip>

> > Which MIPS processor are you talking about? They have different
> > pipelining schemes, which give different instruction timings.
>
> MIPS ?? I was unaware that the original poster requested MIPS code.

Nor did he request Pentium code. Nor VAX, nor IBM 7094. Which was my
point; he was looking for an *algorithm*. Since he expressed his
current algorithm in C, it was a bit rash to assume a particular
processor and give him assembler code. It would have been just as
valid for me to post MIPS assembler, since that's what I normally work
on.

[Eric Bloodworth]

Stephen Westin wrote:
>
> In article <334427...@rrinc.com> Eric Bloodworth <er...@rrinc.com> writes:
>
> <snip>
>
> > You could avoid branching by forming a 4 bit index with a
> > "1" whereever a nonzero byte occurs, looking up an
> > appropriate shift. Here is the 2 byte case, extend
> > as necessary to either 4 bytes or 2 16 bit words:
> >
> > int shift_table[] = { 0, 0, 8, 8 };
> > index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));
>
> ^ That's a conditional; it's
> actually a branch.
>
> > shift = shift_table[index];
> > bit = shift + Ftable[(val >> shift ) & 0xff];
>
> But you *did* cut down to one branch...

Could you please explain how a bitwise or would involve branching?

-- Eric

[Wayne Cochran - CS]

In article <SWESTIN.97...@dsg145.nad.ford.com>, swe...@dsg145.nad.ford.com (Stephen Westin ) writes:
|> In article <334427...@rrinc.com> Eric Bloodworth <er...@rrinc.com> writes:
|>
|> <snip>
|>

|> > You could avoid branching by forming a 4 bit indewith a

|> > "1" whereever a nonzero byte occurs, looking up an
|> > appropriate shift. Here is the 2 byte case, extend
|> > as necessary to either 4 bytes or 2 16 bit words:
|> >
|> > int shift_table[] = { 0, 0, 8, 8 };
|> > index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));
|>
|> ^ That's a conditional; it's
|> actually a branch.

No -- that is a bitwise OR

|>
|> > shift = shift_table[index];
|> > bit = shift + Ftable[(val >> shift ) & 0xff];
|>
|> But you *did* cut down to one branch...
|>

|> <snip>
|>

Does the Pentium chip have a rmo (rightmost one) instruction?
I guess not (the TMS340x0 chips do -- a single clock instruction).
Easy to implement in hardware.

-- wayne
Wayne O. Cochran
wcoc...@eecs.wsu.edu
http://www.eecs.wsu.edu/~wcochran
Ecclesiastes 3:11

[Stephen Westin]

> > > index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));
> >
> > ^ That's a conditional; it's
> > actually a branch.
> >

> Could you please explain how a bitwise or would involve branching?

*PUBLIC APOLOGY FOLLOWS*

Sorry, I posted before thinking. I somehow read that logical
expression as a conditional of the form ( a ? b : c ).

[Neuralog]

This may be dog slow, but I think its quite a cool snippit.

i=0;
while((num_colors-1) >> ++i);
bits_per_color = i;

Ken Land

[Defee Pawel]

In article <SWESTIN.97...@dsg145.nad.ford.com>,
Stephen Westin <swe...@dsg145.nad.ford.com> wrote:

Could someone explain what does the !!( expression ) in the source code
mean? I am talking about the code posted as an answer to the above
question. Though I have seen hundreds of thousands of lines of C code
before, I have never seen the !!() used before...

Regards,
Pawel Defee
--
*******************************************************************************
Pawel Defee
E-mail: pawel...@cc.tut.fi
*******************************************************************************

[Eric Bloodworth]

Ian Kemmish wrote:

>
> However, it is true that CPUs which don't have a `set register from CC
> register' or a `compare and set register' will generate branches (plural) when
> compiling this expression.

True enough. Any idea how many major CPUs don't have this capability?

>
> It is also true that the result of ! is undefined except in so far as it is
> zero or non-zero. On a machine where !0 == ~0, the code fragment wouldn't work
> at all.

From A7.4.7, ANSI K&R:

The operand of the ! operator must have arithmetic type or be a pointer,
and the
result is 1 if the value of its operand compares to 0, and 0 otherwise.
The type
of the result is int.

This conflicts with your second statement.

-- Eric

[Ian Kemmish]

In article <SWESTIN.97...@dsg145.nad.ford.com>,
swe...@dsg145.nad.ford.com says...

>
>
>> > > index = ((!!((val >> 8)&0xff)) << 1) | (!!(val & 0xff));
>> >
>> > ^ That's a conditional; it's
>> > actually a branch.
>> >
>> Could you please explain how a bitwise or would involve branching?
>
>*PUBLIC APOLOGY FOLLOWS*
>
>Sorry, I posted before thinking. I somehow read that logical
>expression as a conditional of the form ( a ? b : c ).

However, it is true that CPUs which don't have a `set register from CC

register' or a `compare and set register' will generate branches (plural) when
compiling this expression.

It is also true that the result of ! is undefined except in so far as it is

zero or non-zero. On a machine where !0 == ~0, the code fragment wouldn't work
at all.

============================================================================
Ian Kemmish 18 Durham Close, Biggleswade, Beds SG18 8HZ
i...@five-d.com Tel: +44 1767 601 361 Fax: +44 1767 312 006
Info on Jaws and 5D's other products on http://www.five-d.com/5d
============================================================================
`Save string while you're young. Then when you're older, you'll have a ball.'

[Tom Duff]

> It is also true that the result of ! is undefined except in so far as it is
> zero or non-zero. On a machine where !0 == ~0, the code fragment wouldn't work
> at all.

It's not the case that the result of ! is undefined. See page 42 of
K&R, second
edition, about 13 lines down from the top. !0 is 1, always. For
nonzero n, !n
is 0, always. As it happens, the language definition does not rule out
a machine
on which ~0 is 1, but that would be perverse in the extreme. In that
case, the
code fragment (not quoted here) would probably not work, but not for the
reason
you imply.
--
Tom Duff

[bou...@smtpg.compsys.com]

wcoc...@eecs.wsu.edu (Wayne Cochran - CS) wrote:
<snip>
>Does the Pentium chip have a rmo (rightmost one) instruction?

the expression (n & -n) returns the least-significant 1 in an integer
ktb

[Chris Rossall]

swe...@dsg145.nad.ford.com (Stephen Westin ) wrote:

>In article <01bc4065$d4036c80$5a43...@prs6id9y.prestel.co.uk> "Slaine" <sla...@eternal.prestel.co.uk> writes:
>

>> Hi,
>>
>> Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan reverse)
>>
>> mov eax, 84h
>> bsr ebx, eax ;gives ebx =7
>>
>> ...a bit of inline should suffice
>>
>> These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71) and
>> not pairable. Compared to code tho.......
>

>Which MIPS processor are you talking about? They have different
>pipelining schemes, which give different instruction timings.
>

>--

Looks like Intel X86 code to me.

-Chris

[Steve Critchlow]

On 2 Apr 1997 21:26:43 GMT, "Dann Corbit" <dco...@solutionsiq.com>
wrote:

>/***********************************************/
>/* Locate the position of the highest bit set. */
>/* A binary search is used. The result is an */
>/* approximation of log2(n) [the integer part] */
>/***********************************************/

<code snipped>

The definition of an IEEE floating point number is:
1.xxxx * pow(2,n)

Basically, if you convert the integer to a floating point number, and
extract the exponent, you will have the value of 'n' you require.

The following functions demonstrate:

/*
* This is the fully portable version, which uses
* the 'frexp' function to get the mantissa and
* exponent of a number.
*/
int getmsb1 ( unsigned long value )
{
int exponent ;
double d_val = (double)value ;
double mantissa = frexp ( d_val, &exponent ) ;
return exponent - 1 ;
}

/*
* This is the rather less portable version, which
* requires you to know how doubles are stored
* in memory, and the location and bias of the
* exponent for such numbers.
* This example is for doubles ( 64 bits )
* on Intel hardware - YMMV.
*/
#define MP(x) ((long int *)&d_val)[x]
int getmsb2 ( unsigned long value )
{
double d_val = (double)value ;
return (int)( MP(1) >> 20 & 0x7ff ) - 0x3ff ;
}

Of course, now you have to weigh up the cost of using floating point
stuff (vs. shifts, branches, masks etc). If all you have is an
emulator, then it's going to be lousy, whereas if you have a pentium
or something like it, and a decent compiler capable of scheduling
instructions properly, then it could be pretty quick. For a start,
there are no branches to clog up those pipelines.

--
Steve

[Neil Moore]

wcoc...@eecs.wsu.edu (Wayne Cochran - CS) writes:
> Does the Pentium chip have a rmo (rightmost one) instruction?

> I guess not (the TMS340x0 chips do -- a single clock instruction).
> Easy to implement in hardware.

In this case, you're looking for the leftmost, not rightmost, bit
(I assume from the subject; I didn't get a chance to read the original
message).

The ix86 instruction for this is BSR (0Fh BDh), available in the
386 and up. The following is taken from _Programming_the_80386_
by John H. Crawford and Patrick P. Gelsinger, published by Sybex,
ISBN 0-89588-381-3.

Formats:
BSR op1, op2
reg16, reg16
reg16, mem16
reg32, reg32
reg32, mem32

Description:

The word or dword specified by op2 is scanned from left to right
(bit 31 or 15 to bit 0) for the first 1 bit. The index of the first
1 bit when scanning left to right is stored in op1.
If the entire word or dword is 0, the ZF bit is set and op1 is
undefined. If a 1 bit is found, the ZF bit is reset.

BTW, I don't have clock timings for Pentia and 486es, but the
386 executes this in 10+3n clocks -- I would assume n is equal
to the result or the result plus 1. By comparison, an eight-bit
by eight-bit MUL takes 9-14 clocks.

(I really need to get a newer x86 reference book :)

Of couse, simply using "BSR CX, AX" isn't really an algorithm...
as such, I've set followups to myself.

--
-Neil Moore http://www.sfhs.floyd.k12.ky.us/~amethyst/
(finger amet...@valjean.sfhs.floyd.k12.ky.us for my Geek Code)

[Firth, Reginald J.]

<< You could avoid branching by forming a 4 bit index with a

<< "1" whereever a nonzero byte occurs, looking up an
<< appropriate shift. Here is the 2 byte case, extend
<< as necessary to either 4 bytes or 2 16 bit words:

Don't be stupid. That will cause an error on the offset. Mail me for
help.

Reg Firth

[Firth, Reginald J.]

rm *

Reg Firth

[Matt Grice]

Slaine <sla...@eternal.prestel.co.uk> wrote in article
<01bc4065$d4036c80$5a43...@prs6id9y.prestel.co.uk>...

> Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan reverse)
> mov eax, 84h
> bsr ebx, eax ;gives ebx =7
> ...a bit of inline should suffice
> These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71)
and
> not pairable. Compared to code tho.......
>

> Cheers
> Slaine

Are these 486 timings? I dont have the pentium databook handy but a
Cyrix 6x86 does BSR/BSF in 4 clocks and I would expect a Pentium to be at
least somewhat competitive. After all, it isn't the hardest operation to
implement in hardware. Then again I don't suppose it's a very commonly
used instruction, either.

If your processor has a BSR of this quality then no C code is going to
approach it.

-Matt

[James Shaw]

"Matt Grice" <mgr...@iastate.edu> wrote:

Erm, the Pentium specs make this a little less cut and dried.

BSF
r16,r/m16 6-34/6-35
r32,r/m32 6-42/6-43

BSR
r16,r/m16 7-39/7-40
r32,r/m32 7-71/7-72

These instructions missed out on optimization in the pentium, hence
the really shite clock times. They probably don't pair properly
either, so a well crafted algorithm could beat this in the average
case (random integers).

Jim

[Slaine]

Matt Grice <mgr...@iastate.edu> wrote in article
<01bc4911$d75b7c60$d74e...@friley215.res.iastate.edu>...

> Slaine <sla...@eternal.prestel.co.uk> wrote in article
> <01bc4065$d4036c80$5a43...@prs6id9y.prestel.co.uk>...
> > Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan reverse)
> > mov eax, 84h
> > bsr ebx, eax ;gives ebx =7
> > ...a bit of inline should suffice
> > These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71)
> and
> > not pairable. Compared to code tho.......
> >
> > Cheers
> > Slaine
>
> Are these 486 timings? I dont have the pentium databook handy but a
> Cyrix 6x86 does BSR/BSF in 4 clocks and I would expect a Pentium to be at
> least somewhat competitive. After all, it isn't the hardest operation to
> implement in hardware. Then again I don't suppose it's a very commonly
> used instruction, either.

Nope. Pentium timings. I was shocked at how slow it was.
------------------------------------------------------------
Cheers
Slaine
Eternal Developments
slaine at eternal dot prestel dot co dot uk

[Dann Corbit]

/**********************************************/
/* I don't remember who suggested this one... */
/* Please email me, so I can give you credit. */
/**********************************************/
int klog2(unsigned long n)
{
register int p = 16,
i = 0;
do {
unsigned long t = n >> p;
if (t)
n = t, i |= p;
} while (p >>= 1);
return i;
}

/* Suggested by:
** Robert E. Minsk[SMTP:egb...@spimageworks.com]
** Similar suggestions from others...
*/
static unsigned char hiBitSetTab[] = {

0, 1, 2, 2, 3, 3, 3, 3,

4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7
};

/* On my machine unsigned int is 32-bits, big ended */
int ulog2(unsigned long val)
{
unsigned long tmp;

tmp = val >> 24;
if (tmp) {
return hiBitSetTab[tmp] + 23;
}

tmp = (val >> 16) & 0xff;
if (tmp) {
return hiBitSetTab[tmp] + 15;
}

tmp = (val >> 8) & 0xff;
if (tmp) {
return hiBitSetTab[tmp] + 7;
}

return hiBitSetTab[val & 0xff]-1;
}

unsigned long zlog2(unsigned long l)
{
unsigned long retval;
_asm mov eax, l ; store number to test in eax
_asm bsr ebx, eax ; gives ebx = high bit
_asm mov retval, ebx;
return retval;
}
Timing results:

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
4127.845 47.6 8676.372 100.0 1 _main (log2.obj)
981.955 11.3 981.955 11.3 1000100 @tlog2@4 (log2.obj)
894.835 10.3 894.835 10.3 1000100 @vlog2@4 (log2.obj)
801.445 9.2 801.445 9.2 1000100 @qlog2@4 (log2.obj)
641.140 7.4 641.140 7.4 1000100 @klog2@4 (log2.obj)
637.275 7.3 637.275 7.3 1000100 @ulog2@4 (log2.obj)
591.877 6.8 591.877 6.8 1000100 @zlog2@4 (log2.obj)

James Shaw <j...@curved-logic.com> wrote in article
<3353436c...@snews2.zippo.com>...

>
> "Matt Grice" <mgr...@iastate.edu> wrote:
>
> >
> >
> >Slaine <sla...@eternal.prestel.co.uk> wrote in article
> ><01bc4065$d4036c80$5a43...@prs6id9y.prestel.co.uk>...
> >> Use the BSF or BSR routines.....(Bit Scan Forward and Bit Scan
reverse)
> >> mov eax, 84h
> >> bsr ebx, eax ;gives ebx =7
> >> ...a bit of inline should suffice
> >> These instructions are extremely slow (bsf is 6-42 ticks, bsr is 7-71)
> >and
> >> not pairable. Compared to code tho.......
> >>
> >> Cheers
> >> Slaine
> >
> >Are these 486 timings? I dont have the pentium databook handy but a
> >Cyrix 6x86 does BSR/BSF in 4 clocks and I would expect a Pentium to be
at
> >least somewhat competitive. After all, it isn't the hardest operation
to
> >implement in hardware. Then again I don't suppose it's a very commonly
> >used instruction, either.
> >

[Tim Sweeney]

Dann Corbit <dco...@solutionsiq.com> wrote in article
<01bc4b63$31919040$ca61...@DCorbit.solutionsiq.com>...
>(bunch of cool routines deleted)

Another interesting approach is to use the FPU, which automatically
computes the index of the highest bit, using something like this:

Input DD 0
Temp DD 0
Output DB 0 ; log 2 of input

fild [Input] ; 4 cycles?
xor eax,eax ; free
fst [Output] ; 3 cycles
mov eax,[Output] ; 1 cycle
and eax, ??? ; 1 cycle, the value of ??? is left as an excercise to the
reader. :)
shr eax, ??? ; 1 cycle
add eax, ??? ; 1 cycle adjust for exponent bias.
; The idea of the above is to extract the exponent.

This would always be about 11 cycles, and I reckon it would be faster than
the other methods posted, because their average case performance suffers
from branch misprediction penalties which are pretty expensive especially
on PentiumPro class processors.

-Tim Sweeney, Epic MegaGames Inc.