Help - How to get the most significant bit
Author
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
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;
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.
I'll learn to read one of these days... WITHOUT while loops... a look up table would work fine... not sure what else...
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
A binary search type approach could yield O(log n). That's probably the best you can do without a huge lookup table.
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
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
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
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?
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
