/***********************************************/
/* Locate the postion 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;
}
//
// int             jlog2(int a)
// {
//     int             b;
//     b = -1;
//     while (a > 0) {
//         a = (a >> 1);
//         b++;
//     }
//     return (b);
// }
// #define BITS 32
// int             klog2(int a)
// {
//     int             p,
//                     try,
//                     cur,
//                     res;
//     cur = a;
//     res = 0;
//     for (p = BITS >> 2; p > 0; p >>= 1) {
//         try = cur >> p;
//         if (try > 0) {
//             cur = try;
//             res += p;
//         }
//     }
//     return (res);
// }
// /* --> Don't even think about it.  This one sucks.
// ** int             llog2(unsigned int n)
// ** {
// **     return n ? 1 + llog2(n >> 1) : -1;
// ** }
// */
// static const unsigned char bit[] =
// {
//     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,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
//     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
// };
// int             llog2(unsigned long ulN)
// {
//     union hack_tag {
//         unsigned long   l;
//         char            c4[4];
//     }               a_hack;
//     int             i;
//     int             total = 0;
//     a_hack.l = ulN;
//     for (i = 3; i >= 0; i--) {
//                 total <<= 1;
//         total += bit[a_hack.c4[i]];
//
//     }
//     total--;
//     return total;
// }
// int             nlog2(unsigned int n, int m);
//
// int             mlog2(unsigned int n)
// {
//     return nlog2(n, 32);
// }
// int             nlog2(unsigned int n, int m)
// {
//
//     if (!n)
//         return -1;
//
//     if (m >>= 1)
//         if (n >> m)
//             return m + nlog2(n >> m, m);
//         else
//             return nlog2(n, m);
//     else
//         return 0;
// }
// /*======================================================================*/
// /*
// ** From:   Douglas.Priest@Eng.Sun.COM[SMTP:Douglas.Priest@Eng.Sun.COM]
// ** Sent:   Wednesday, April 02, 1997 3:25 PM
// ** To:     Dann Corbit
// ** Subject:        Re: finding the highest bit set in a 32 bit integer
// **
// ** It depends on the hardware.  On many machines, the fastest way to find
// ** the highest order bit is to convert the integer to a floating point
// ** number and look at the exponent field.  Here are a couple variations
// ** on this idea (assuming "double" is IEEE 754 double precision):
// */
// typedef union {
//     unsigned        x[2];
//     double          d;
// }               double_bits;
//
// #ifdef _LITTLE_ENDIAN
// #define HIWORD  1
// #define LOWORD  0
// #else
// #define HIWORD  0
// #define LOWORD  1
// #endif
//
// /* if n is a nonnegative int, this method should work well on machines
//    that have an integer-to-fp conversion instruction */
// int             olog2( long n)
// {
//     double_bits     d;
//     int             l;
//
//     d.d = n;
//     l = (d.x[HIWORD] >> 20) & 0x7ff;
//     return (l ? l - 0x3ff : -1);
// }
//
// /* for unsigned n, this method should work well on most machines, even
//    if they don't have an unsigned-int-to-fp conversion instruction */
// int             plog2(unsigned long n)
// {
//     double_bits     d1,
//                     d2;
//
//     d1.x[HIWORD] = d2.x[HIWORD] = 0x03500000;
//     d1.x[LOWORD] = 0;
//     d2.x[LOWORD] = n;
//     d2.d -= d1.d;
//     return ((d2.x[HIWORD] >> 20) & 0x7ff) - 1;
// }
// /*
// ** Of course, these examples rely on behavior not guaranteed by ANSI C,
// ** but they should work on most systems, and they may well be faster than
// ** your code.
// **
// ** Regards,
// **
// ** Douglas M. Priest
// ** SunSoft Floating Point Group
// ** Sun Microsystems, Inc.
// ** (but only speaking for myself)
// */
//
/*======================================================================*/
/*
** From: <bousek@$smtpg.compsys.com$>
** Subject: Re: Is there a faster way to find the highest bit set in a 32 bit integer? [Includes C code listing]
** Newsgroups: comp.graphics.algorithms
** References: <01bc3fac$69b314c0$ca61e426@DCorbit.solutionsiq.com>
** Organization: TDS Telecom - Madison, WI
** Message-ID: <01bc405b$2c1c8740$ca61e426@DCorbit.solutionsiq.com>
** X-Newsreader: Microsoft Internet News 4.70.1155
** MIME-Version: 1.0
** Content-Type: text/plain; charset=ISO-8859-1
** Content-Transfer-Encoding: 7bit
**
** "Dann Corbit" <dcorbit@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            qlog2(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            rlog2(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            slog2(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... :-( )
// **
// */
// /*======================================================================*/

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;
}
#include <math.h>
/*
 * FROM: steve@tangled-web.compulink.co.uk
 * This is the fully portable version, which uses
 * the 'frexp' function to get the mantissa and
 * exponent of a number.
 */
int slog2( unsigned long value )
{
   int      exponent ;
   double   d_val = (double)value ;
   double   mantissa = frexp ( d_val, &exponent ) ;
   return exponent - 1 ;
}

/*
 * FROM: steve@tangled-web.compulink.co.uk
 * 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.
 */
/* CHANGED FROM DOUBLE TO FLOAT --
#define MP(x)  ((long int *)&d_val)[x]
int tlog2( unsigned long value )
{
   double d_val = (double)value ;
   return (int)( MP(1) >> 20 & 0x7ff ) - 0x3ff ;
}
*/
#define MP(x)  ((unsigned long *)&d_val)[x]
int tlog2( unsigned long value )
{
   float d_val = (float)value ;
   return (int)( MP(0) >> 23 & 0xff ) - 0x7f ;
}

/*
From:   Robert E. Minsk[SMTP:egbert@spimageworks.com]
Sent:   Saturday, April 12, 1997 9:44 PM
To:     Dann Corbit
Subject:        Is there a faster way to find the highest bit set in a 32 bit integer? [Includes C code listing]

  I did not see the original post but why don't you build a table of the
highest bit set in a byte and then check each byte.  For example.
*/
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;
}

/* On my machine unsigned int is 32-bits, big ended */
int ulog3(unsigned long val)
{
//    unsigned long tmp;
    unsigned char *foo = (unsigned char *) &val;
//    tmp = val >> 24;
    if (foo[3]) {
        return hiBitSetTab[foo[3]] + 23;
    }

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

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

    return hiBitSetTab[foo[0]]-1;
}

/*
or even:
*/
typedef union {
    unsigned long i;
    unsigned char c[4];
} u32bitType;

/* On my machine unsigned int is 32-bits, big ended */
int vlog2(long l)
{
    u32bitType val;
    val.i = l;
    if (val.c[3]) {
        return hiBitSetTab[val.c[3]] + 23;
    }

    if (val.c[2]) {
        return hiBitSetTab[val.c[2]] + 15;
    }

    if (val.c[1]) {
        return hiBitSetTab[val.c[1]] + 7;
    }

    return hiBitSetTab[val.c[0]]-1;
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int             main(void)
{
    unsigned long   l;
    unsigned long   m;
    unsigned long   limit = 1000000;

    for (l = 0; l < limit; l++)
    {
        m = l*rand();
        m =  qlog2(m), klog2(m), slog2(m), tlog2(m), ulog2(m), vlog2(m), ulog3(m);
    }

    for (l = 0; l < limit / 100; l += 100) {
        printf("l=%lu, klog2=%lu, qlog2=%lu, slog2 = %lu, tlog2 = %lu, ulog2 = %lu, vlog2 = %lu, ulog3 = %lu, log2=%f\n",
               l, klog2(l), qlog2(l), slog2(l), tlog2(l), ulog2(l), vlog2(l), ulog3(l), log((double) l) / log(2.));
//      printf("l=%lu, ilog2=%lu, klog2=%lu, llog2=%lu, mlog2=%lu, olog2=%lu, plog2=%lu, qlog2=%lu, rlog2=%lu, slog2=%lu, log2=%f\n", l,
//             ilog2(l), klog2(l), llog2(l), mlog2(l), olog2(l), plog2(l), qlog2(l), rlog2(l), slog2(l),
//             log((double) l) / log(2.));
    }
    return 0;
}
#endif