I figured there had to be a really, really fast way to do it.
For the binary search method, I was just thinking that for a 32 bit number, you "or" the first 16 bits and see if there is a 1 in there. Then narrow the search down to 8 bits in either the first or second half. Then repeat until you find a 1 or you don't. Five or six comparisons. I'll take the other way any day.
Help - How to get the most significant bit
Quote:Original post by FlowingOozeQuote: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.
Look closer.
Look at the worked eg i used.
Do what i did.
From,
Nice coder
Thinking about the problem, I don't think any method, short of the look up table, is going to get you any better performance than O(b), where b is the number of bits that represent the number. The reason being that you have to look at every bit in the number, from MSB to LSB, in order to see whether it is 1 or 0. There's no way you can skip a bit without leaving the opportunity that your answer will be wrong.
So in summary, zeelot, I think you are either forced to use a lookup table or use one of the O(b) algorithms to get the answer.
So in summary, zeelot, I think you are either forced to use a lookup table or use one of the O(b) algorithms to get the answer.
Quote:Original post by ascorbic
I figured there had to be a really, really fast way to do it.
For the binary search method, I was just thinking that for a 32 bit number, you "or" the first 16 bits and see if there is a 1 in there. Then narrow the search down to 8 bits in either the first or second half.
That would work, but it would be hard on branch prediction, also you'd have a to generate the mask and keep track of the bit, probably would take more instructions total than a simple loop for 32-bits.
Quote:Original post by Nice Coder
Look closer.
Look at the worked eg i used.
Do what i did.
Oops. You're right. Anyways it doesn't solve the problem of finding the MSB. It just clears the rest of the bits. Also you've got an overflow problem if the MSB is the 31th bit (counting from 0). You need to test for zero, before and after.
Quote:Original post by ascorbic
I figured there had to be a really, really fast way to do it.
For the binary search method, I was just thinking that for a 32 bit number, you "or" the first 16 bits and see if there is a 1 in there. Then narrow the search down to 8 bits in either the first or second half. Then repeat until you find a 1 or you don't. Five or six comparisons. I'll take the other way any day.
Yep. Assuming a comparison ain't that expencive, its one of the best options.
The best option is a lut assisted binary search.
My best would be only a few comparisons. (ie. somewhere near three), and a 256 element lut.
Assume you have a 32 bit number.
First you test the first 16 bits. (jz, no cmp needed. Use the 16 bit registers)
Then if its true, then you try the first 8 bits. (another jz).
If that doesn't work, then you just use the lut on the output.
If the first 16 bits are false, then you just try the other way. (same thing, just using different registers).
i'm pretty sure an optimised asm version would be superfast.
From,
Nice coder
The methods we've come up with so far do find the bit (ex: 0100 0000 0000 0000), but doesn't address the OP's need to know exactly which bit number it is.
Maybe O(n) is the best solution to the problem. Or not... I've reached my level of incompetence for the night.
EDIT: Working in hand coded assembly with all the branching you could return the bit number.
Maybe O(n) is the best solution to the problem. Or not... I've reached my level of incompetence for the night.
EDIT: Working in hand coded assembly with all the branching you could return the bit number.
Quote:Original post by FlowingOozeQuote:Original post by Nice Coder
Look closer.
Look at the worked eg i used.
Do what i did.
Oops. You're right. Anyways it doesn't solve the problem of finding the MSB. It just clears the rest of the bits. Also you've got an overflow problem if the MSB is the 31th bit (counting from 0). You need to test for zero, before and after.
Hmm.
Ok, it looks like i misread the question...
This makes it a whole lot harder.
Wtf do you want the msb AS A NUMBER for?
From,
Nice coder
Quote:Original post by FlowingOoze
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?
My method can find it in o(log2(log2(n)) where n is the biggest number that you want it to use.
From,
Nice coder
Quote:Original post by Nice Coder
Yep. Assuming a comparison ain't that expencive, its one of the best options.
The best option is a lut assisted binary search.
My best would be only a few comparisons. (ie. somewhere near three), and a 256 element lut.
Assume you have a 32 bit number.
First you test the first 16 bits. (jz, no cmp needed. Use the 16 bit registers)
Then if its true, then you try the first 8 bits. (another jz).
If that doesn't work, then you just use the lut on the output.
If the first 16 bits are false, then you just try the other way. (same thing, just using different registers).
i'm pretty sure an optimised asm version would be superfast.
From,
Nice coder
ARM doesn't have 16-bit subregisters. Other than that, this approach is worth trying and does actually return the MSB bit number. However one should not forget the penalty incurring from a cache miss when accessing the lut.
Though I still don't understand why anyone would need something like this when a three instruction loop does the trick in no more that 32 iterations.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
