# 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.

## 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 on other sites
How about something like this... at least it's a start.

int done = 0;int bit = 17;int testPattern = 0xFF; // or whatever in hex codeint mask = 0x80;while(!done){     done = testPattern & mask;     mask >>= 1;     bit--;}return bit;

##### 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 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 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 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 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 on other sites
Quote:
 Original post by ascorbicA 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.

From,
Nice coder

##### 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 on other sites
Quote:
 Original post by Nice Codermsb = 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.

1. 1
2. 2
3. 3
4. 4
Rutin
12
5. 5

• 12
• 16
• 10
• 14
• 10
• ### Forum Statistics

• Total Topics
632659
• Total Posts
3007692
• ### Who's Online (See full list)

There are no registered users currently online

×