C#

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 ] ) ;
}

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

private byte Log2(ulong val) {
    int res = -1;
    if (val  > 0xFFFFFFFF) { res += 32; val >>= 32; }
    uint val2 = (uint)val;
    if (val2 > 0x0000FFFF) { res += 16; val2 >>= 16; }
    if (val2 > 0x000000FF) { res +=  8; val2 >>=  8; }
    if (val2 > 0x0000000F) { res +=  4; val2 >>=  4; }
    return (byte)(res + s_Array[val2]);
}

                           Gross    Net
Cascading Types:          1046 ms  591 ms
Hard Coded Conditionals:   760 ms  305 ms
Hard Coded Cond. W/ Array: 593 ms  138 ms
Control:                   455 ms    0 ms

Skippums wrote:

using your idea

private static readonly byte[] highestbitset = new byte[]
{
    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
} ;

public static int
HighestBitSet
(
    byte Subject
)
{
    return ( highestbitset [ Subject ] ) ;
}

PIEBALDconsult wrote:

Notice the name change

Luc Pattyn wrote:

straight table lookup

switch ( x ) 
{
case 255 :
...
case 128 : return 8 ; break ;

...
}

PIEBALDconsult wrote:

Put the noose away!

Luc Pattyn wrote:

How would this be faster?

Luc Pattyn wrote:

you have chosen to confuse the reader by giving them all the same name.

Luc Pattyn wrote:

not the highest bit set.

PIEBALDconsult wrote:

Well if given a byte, ushort, or uint it wouldn't need to convert them to ulong before beginning

PIEBALDconsult wrote:

Of course; they all do the same thing

PIEBALDconsult wrote:

I need a head start

Luc Pattyn wrote:

since they would be private
methods

Skippums wrote:

Is there a better way to do this, like perhaps a binary search algorithm?