Jump to content
  • Advertisement
Sign in to follow this  
zeelot

Help - How to get the most significant bit

This topic is 4824 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

We are developing game engine on ARM CPU... Here is a problem we have. There is a binary number (stuff like "00101011"). We need to know WHICH bit is its MSB (Most Significant Bit). In the above example, the answer is "6". The problem is: Is it possible to figure out the answer without FOR/WHILE or LOG... - bit operations are preferred - O(1) operation Thanks everybody zEELOt

Share this post


Link to post
Share on other sites
Advertisement
How about something like this... at least it's a start.


int done = 0;
int bit = 17;
int testPattern = 0xFF; // or whatever in hex code
int mask = 0x80;

while(!done)
{
done = testPattern & mask;
mask >>= 1;
bit--;
}
return bit;




Share this post


Link to post
Share on other sites
If you are only dealing with 8 bits, you could just store all the values in a lookup table for the fastest execution; unless there's a really obvious solution that I haven't spotted at first glance.

Share this post


Link to post
Share on other sites
I'll learn to read one of these days... WITHOUT while loops... a look up table would work fine... not sure what else...

Share this post


Link to post
Share on other sites

msb = number;
msb |= msb >> 1;
msb |= msb >> 2;
msb |= msb >> 4;
msb |= msb >> 8;
msb |= msb >> 16;
msb = (++msb)>>1;


ok?

There are faster ways to do it tho.... (many faster ways).

From,
Nice coder

Share this post


Link to post
Share on other sites
A binary search type approach could yield O(log n). That's probably the best you can do without a huge lookup table.

Share this post


Link to post
Share on other sites
To explain.

Lets say you had the number 0010001101

First stage
0010001101 |= 0010001101 >> 1
= 0010001101 | 0001000110

0010001101
0001000110
----------
0011001111

Second stage
0011001111 | 0011001111 >> 2
0011001111
0000110011
0011111111

Next stage....
(they don't make any difference, because of the number. you could use some special cases to increase its speed a bit, but they might not work well (speed vs clutter)).

And the end.

0011111111
+ 1
=
0100000000
Leftshift one
0010000000
Compare to our number
0010001101

See any similarities?
Yes, its its msb.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by ascorbic
A binary search type approach could yield O(log n). That's probably the best you can do without a huge lookup table.


My current version does 12 ops (all bitwise) for a 32 bit number. (two more for a 64 bit number, ect)

For your o(log n) solution to be better, you'd need a S of less then

S(5) < 12
S < 12/5
S < 2.4

So, you need 2.4 operations per iteration AT MOST. (ie. to break even).

A single if is more then 2.4 operations.

There was a thread about this.... (next biggest power of two... thread, i don't have a link and i'm not gonna battle google to find it).

From,
Nice coder

Share this post


Link to post
Share on other sites
ascorbic: How would you do a binary search?
Nice Coder: That's a clever idea, but you'd better test it to be sure that it's any faster than a simple loop. Also it doesn't answer the question.

zeelot: What do you need the msb for? Does it really make any difference if you use the method ascorbic posted?

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder

msb = number;
msb |= msb >> 1;
msb |= msb >> 2;
msb |= msb >> 4;
msb |= msb >> 8;
msb |= msb >> 16;
msb = (++msb)>>1;



Doesn't work btw.

100000b>>0 | 100000b>>1 | 100000b>>2b | 100000b>>4b =
100000b | 10000b | 1000b | 10b =
111010b

You need to have all of the bits:

msb |= msb >> 1;
msb |= msb >> 2;
msb |= msb >> 3; // <---
msb |= msb >> 4;
msb |= msb >> 5; // <---
....


On ARM I think you can code each line with one instruction. A loop would take 3 instructions, at an average of 1.5 per bit, assuming all integers are equally likely and would also give the answer that was asked for, ie. the MSB-bit. Due to instruction scheduling and caching, it would be best to test either case, or just use the loop for simplicity and smaller size.

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!