Efficient way of finding most-significant non-zero bit of integer

[Rich Townsend]

Hi all --

In writing some logic code for an octree, I've come across a situation where I
have to find the most-significant non-zero bit of an integer.

I can see how this might be done via a brute-force scan through the bits:

integer :: mynumber,i

do i = BIT_SIZE(i),1,-1
if(BTEST(mynumber,i-1)) exit
enddo

But can anyone suggest a more-efficient way of doing this? Essentially, I'm
looking for an integer log_2() function.

cheers,

Rich

[James Van Buskirk]

"Rich Townsend" <rh...@barVOIDtol.udel.edu> wrote in message
news:gbas42$jeu$1...@scrotar.nss.udel.edu...

> In writing some logic code for an octree, I've come across a situation
> where I have to find the most-significant non-zero bit of an integer.

Hardware normally has an instruction to do just this. F08 has the
LEADZ intrinsic to encourage the compiler to map directly to the
appropriate machine instruction. See also TRAILZ. Since the cost
of implementation is about zilch you might find that compilers you
are interested in may already have these intrinsics. ifort for
example has had them for years.

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

[Tim Prince]

Louis Krupp wrote:

> You might be able to try what's essentially a binary search. For an
> eight-bit integer, it would look something like this:
>
> if (n .ge. 2 ** 4) then
> if (n .ge. 2 ** 6) then
> if (n .ge. 2 ** 7) then
> i = 7
> else
> i = 6
> endif
> else if (n .ge. 2 ** 5) then
> i = 5
> else
> i = 4
> endif
> else ...
>
> You'd have log_2(BITSIZE(n)) comparisons.
>
Binary search proposals showed up in a Google search. If you want it
faster, at the expense of slightly more code + data:
Assuming that your compiler supports byte addressing, you could find the
highest order non-zero byte. Use its value as an index into a
pre-computed table. Shift the result from your table up according to the
index of that byte.

[ttw...@att.net]

I've done this two ways. The first is to shift and mask to check each
byte (starting with the most significant) then use a table lookup to
get the leading bit. It takes a table of 256 entries.

The second is the (previously suggested) binary search. Check if
greater than 2**16 then either 2**24 or 2*8, etc. One can use a 32 (or
31 depending on various things) long table for better speed. Or one
could shift a 1 into place for the comparison.

Both are easy to code and resaonably fast.

[Rich Townsend]

James Van Buskirk wrote:
> "Rich Townsend" <rh...@barVOIDtol.udel.edu> wrote in message
> news:gbas42$jeu$1...@scrotar.nss.udel.edu...
>
>> In writing some logic code for an octree, I've come across a situation
>> where I have to find the most-significant non-zero bit of an integer.
>
> Hardware normally has an instruction to do just this. F08 has the
> LEADZ intrinsic to encourage the compiler to map directly to the
> appropriate machine instruction. See also TRAILZ. Since the cost
> of implementation is about zilch you might find that compilers you
> are interested in may already have these intrinsics. ifort for
> example has had them for years.
>

Thanks for the suggestion. For the gfortran gurus in the forum, how can I submit
a feature request to get these routines implemented?

cheers,

Rich

[Craig Powers]

The mailing list and/or Bugzilla (and if you omit one of those, it
should probably be the mailing list).

[Terence]

Fastest is use of Assemler - one instruction (number of highest bit),
but non-intrinsic has subroutine./function penalty.
Next best is (for 64 bits)
Bit Power= 3*16=48
Locate first non-zero byte from high byte to low byte (a 4 times loop)
and subtract 16 for finding zero.
Else get corresponding integer from 256 word look-up table using first
nonzero byte as index offset, add to current "Bit Power".

The 256 word integer table would contain the byte power contributions
15,14,14........1,0

[steven....@gmail.com]

On Sep 23, 6:53 pm, Rich Townsend <r...@barVOIDtol.udel.edu> wrote:
> James Van Buskirk wrote:

> > "Rich Townsend" <r...@barVOIDtol.udel.edu> wrote in message

They are now implemented (I hope I made no mistakes ;-). Snapshots and
precompiled binaries newer than today should include LEADZ and TRAILZ.

Gr.
Steven