Re: Need help in solving compile-time log2

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-05-16 23:01:37

on 5/12/01 6:10 AM, Daryle Walker at darylew_at_[hidden] wrote:

> In the vault there is a version 0 of "dlw_int.zip".  The "integer_mask.hpp"
> header takes ideas from my CRC classes.  The second header, "static_lb.hpp",
> uses the first header in determining the log-2 of a value at compile-time.
> There is a "lb_test.cpp" test/example file.  Everything looked good until I
> tried higher numbers.  The last three tests gave answers of 7, 4, and 4
> instead of 9, 10, and 10 respectively.  Help!

I think I got the problem partially licked by taking a different course.  I
tried writing a regular function version of this routine so I can debug it.
I'm now using something like this:

//=======================================================================
// Need to simulate this as a template for compile-time processing
int
dynamic_lb( unsigned long val )
{
    int  place = 0;
    for ( int i = std::numeric_limits<unsigned long>::digits ; i > 0
     ; i /= 2 )
    {
        int const            half_place = i / 2;
        unsigned long const  lower_mask = (1ul << half_place) - 1;
        unsigned long const  upper_mask = ~lower_mask;
        if ( (val & upper_mask) != 0 )
        {
            val >>= half_place;
            place += half_place;
        }
    }
    return place;
}
//=======================================================================

Now, how would I convert this to a template "routine" so I can compute this
for a compile-time constant?  Also, would it work if an "unsigned long" had
a bit count that wasn't a power of two?  (That would necessitate at least
one odd number halving.  Would it be better to keep the larger or smaller
part?)  Maybe we should get those compile-time IFs and FORs up and running.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com