C#

Skippums wrote:

like perhaps a binary search algorithm?

private byte Log2_2(uint val) {
    if (val < 1)
        return byte.MaxValue;
    byte high = sizeof(uint) << 3;
    byte low  = 0, med = (byte)(high >> 1);
    uint tmp = val >> med;
    while (tmp != 1) {
        if (tmp == 0)
            high = med;
        else
            low  = med;
        med = (byte)(low + high >> 1);
        tmp = val >> med;
    }
    return med;
}

int LP_log2_3(uint val) {
    if(val==0) return -1;
    int res=0;
    if(val>0x0000FFFF) {res+=16;val>>=16;}
    if(val>0x000000FF) {res+=8;val>>=8;}
    if(val>0x0000000F) {res+=4;val>>=4;}
    if(val>0x00000003) {res+=2;val>>=2;}
    if(val>1) res++;
    return res;
}

                               Gross     Net
1. Linear search:             1542 ms  1091 ms
2. Binary search:              887 ms   436 ms
3. Hardcoded Conditionals:     686 ms   235 ms
4. Control (returns constant): 451 ms     0 ms

private Stopwatch sw = new Stopwatch();
private List<uint> m_Nums = new List<uint>(0x1000000);
private List<uint> result1 = new List<uint>(0x1000000);
private List<uint> result2 = new List<uint>(0x1000000);
private List<uint> result3 = new List<uint>(0x1000000);
private List<uint> result4 = new List<uint>(0x1000000);
...
private void button1_Click(object sender, EventArgs e) {
    m_Nums.Clear();
    result1.Clear();
    result2.Clear();
    result3.Clear();
    result4.Clear();
    Random rnd = new Random();
    for (int i = 0; i < m_Nums.Capacity; ++i)
        m_Nums.Add((uint)rnd.Next());
// Start "Block1"
    sw.Start();
    foreach (uint num in m_Nums)
        result1.Add(Log2_1(num));
    sw.Stop();
    label1.Text = sw.ElapsedMilliseconds.ToString();
    sw.Reset();
// End "Block1"
// Repeat "Block1" for methods Log2_2, Log2_3, and Log2_4
}

if (val < 1)
    return byte.MaxValue;
int shift = sizeof(uint) << 2;
uint mask = uint.MaxValue >> shift;
int rval = 0;
do {
    if (val > mask) {
        rval += shift;
        val >>= shift;
    }
    shift >>= 1;
    mask >>= shift;
} while (shift > 0);
return (byte)rval;

byte high = sizeof(myType) << 3;
byte med  = (byte)(high >> 1);
byte low  = 0;
myType tmp = val >> med;
while (tmp != 1) {
    if (tmp == 0)
        high = med;
    else
        low  = med;
    med = (byte)(low + high >> 1);
    tmp = val >> med;
}
return med;

byte shift = (byte)(sizeof(myType) << 2);
myType mask = myType.MaxValue >> shift;
byte rval = 0;
do {
    if (val > mask) {
        rval += shift;
        val >>= shift;
    }
    shift >>= 1;
    mask  >>= shift;
} while (shift > 0);
return rval;

byte res = 0;
if (val > 0xFFFFFFFF) { res += 32; val >>= 32; }
if (val > 0x0000FFFF) { res += 16; val >>= 16; }
if (val > 0x000000FF) { res +=  8; val >>=  8; }
if (val > 0x0000000F) { res +=  4; val >>=  4; }
if (val > 0x00000003) { res +=  2; val >>=  2; }
if (val > 0x00000001) ++res;
return res;

           Gross     Net
Method 1  1366 ms   892 ms
Method 2  2093 ms  1619 ms
Method 3   949 ms   475 ms
Control    474 ms     0 ms

Luc Pattyn wrote:

And make it fast!

public static int
MSB
(
    ulong Subject
)
{
    int result = 63 ;

    if ( Subject != 0 )
    {
        ulong runner = 1 ;

        runner <<= result ;

        while ( ( Subject & runner ) == 0 )
        {
            result-- ;
            runner >>= 1 ;
        }
    }
    else
    {
        result = -1 ;
    }

    return ( result ) ;
}

public static int
MSB
(
    ulong Subject
)
{
    return
    (
        Subject > uint.MaxValue
    ?
        MSB ( (uint) ( Subject >> 32 ) ) + 32
    :
        MSB ( (uint) Subject )
    ) ;
}

public static int
MSB
(
    uint Subject
)
{
    return
    (
        Subject > ushort.MaxValue
    ?
        MSB ( (ushort) ( Subject >> 16 ) ) + 16
    :
        MSB ( (ushort) Subject )
    ) ;
}

public static int
MSB
(
    ushort Subject
)
{
    return
    (
        Subject > byte.MaxValue
    ?
        MSB ( (byte) ( Subject >> 8 ) ) + 8
    :
        MSB ( (byte) Subject )
    ) ;
}

public static int
MSB
(
    byte Subject
)
{
    int result = 7 ;

    if ( Subject != 0 )
    {
        byte runner = 128 ;

        while ( ( Subject & runner ) == 0 )
        {
            result-- ;
            runner >>= 1 ;
        }
    }
    else
    {
        result = -1 ;
    }

    return ( result ) ;
}

public static int
HighestBitSet
(
    byte Subject
)
{
    int result = -1 ;

    if ( Subject > 15 )
    {
        Subject >>= 4 ;
        result += 4 ;
    }

    if ( Subject > 3 )
    {
        Subject >>= 2 ;
        result += 2 ;
    }

    if ( Subject > 1 )
    {
        Subject >>= 1 ;
        result += 1 ;
    }

    if ( Subject > 0 )
    {
        result += 1 ;
    }

    return ( result ) ;
}

private static readonly int[] force = new int[]
{ 0 , 1 , 2 , 2 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 } ;

public static int
HighestBitSet
(
    byte Subject
)
{
    int result = -1 ;

    if ( Subject > 15 )
    {
        Subject >>= 4 ;
        result = 3 ;
    }

    return ( result + force [ Subject ] ) ;
}