Jump to content
  • Advertisement
Sign in to follow this  
Ivo Leitao

[.net] HighestBitSet in C#

This topic is 4848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to optimize a a method that returns the highest bit set in a bit pattern, my current code is :
        private int HighestBitSet(int bitPattern)
        {
            return 
                (Convert.ToString(bitPattern, 2).Length - 1)
                - 
                Convert.ToString(bitPattern, 2).IndexOf("1");
        }
I know that in c++ i can use an assembler intruction to do this but in c# is not possible so, how can i optimize this ? Tnks

Share this post


Link to post
Share on other sites
Advertisement
There are lots of optimizations you could do here.

The easiest would be to create a temp string to hold the results of Convert.ToString so you only do the conversion once.

Of course, a series of "if bitPattern && 0x... { return ... }" statements might be faster than the string conversion and search, but would require more code.

Share this post


Link to post
Share on other sites
Quote:
Original post by VizOne
Take a look

Regards,
Andre


Ok this seems to work, now my problem is why ? :-)
I dont't understand the purpose of the two arrays, what's the meaning of the numbers in b and s ?


private static int HighestBitSet(int value)
{
int [] b = {0x2, 0xC, 0xF0, 0xFF00};
int [] s = {1, 2, 4, 8};
int i;

int c = 0; // result of log2(v) will go here
for (i = 3; i >= 0; i--) // unroll for speed...
{
if ((value & b) != 0)
{
value >>= s;
c |= s;
}
}

return c;
}


Update : does not work with Int32 max (2147483647), i think that it only works with an uint and that is not CLS compliant :-(
Update2 : Well I have made some tests and the method that uses a table is the fastest so i will stick with that one, anyway here's the code :


static int [] LogTable256 =
{
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
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,
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,
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
};

private static int HighestBitSet3(int value)
{
int c = 0; // c will be lg(v)
int t, tt; // temporaries

if ((tt = value >> 16) != 0)
{
c = ((t = value >> 24) != 0) ? 24 + LogTable256[t] : 16 + LogTable256[tt & 0xFF];
}
else
{
c = ((t = value >> 8) != 0) ? 8 + LogTable256[t] : LogTable256[value];
}

return c;
}


[Edited by - Ivo Leitao on August 5, 2005 12:12:32 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!