Quote:Original post by FlowingOoze

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.

Quote:Original post by zeelot
We need to know WHICH bit is its MSB (Most Significant Bit).

int ilog2(unsigned int i) {    int b = 0;    if ((i & 0xAAAAAAAA) > (i & 0x55555555)) b++;    if ((i & 0xCCCCCCCC) > (i & 0x33333333)) b += 2;    if ((i & 0xF0F0F0F0) > (i & 0x0f0f0f0f)) b += 4;    if ((i & 0xFF00FF00) > (i & 0x00ff00ff)) b += 8;    if ((i & 0xFFFF0000) > 0) b += 16;    return b;}

int ilog2(unsigned int i) {    int b = 0;    if (i & 0xffff0000) b += 16; else i<<=16;    if (i & 0xff000000) b += 8; else i<<=8;    if (i & 0xf0000000) b += 4; else i<<=4;    if (i & 0xc0000000) b += 2; else i<<=2;    if (i & 0x80000000) b += 1;    return b;}

Quote:Original post by Christer Ericson

Quote:Original post by zeelot
We need to know WHICH bit is its MSB (Most Significant Bit).

There are gazillion ways of doing this. Here is one:

*** Source Snippet Removed ***

Here's another one:

*** Source Snippet Removed ***

Quote:Original post by FlowingOoze
I can't be bothered to lookup ARM instruction set right now, but I think you can do the entire loop in three:

1. Increment MSB bit counter
2. Shift left and set flags
3. Branch if not zero

So it's only 3*31 = 93 instructions and if all integers are equally likely, it's half of that on average, ie. 41.5 . If the MSB is more likely to be small, then it's faster than 41.5 on average. If it's more likely to be bigger, then the loop can be written to shift in the other direction and again get a better average.

I don't know how different ARM processor do branch prediction, but the branch is always taken, except on the last iteration, so it has a pretty good change of getting it right.

Quote:Original post by Christer Ericson

Quote:Original post by zeelot
We need to know WHICH bit is its MSB (Most Significant Bit).

There are gazillion ways of doing this. Here is one:

*** Source Snippet Removed ***

Here's another one:

*** Source Snippet Removed ***

Quote:Original post by Nice Coder
Unfortunatly that doesn't work.

Exersise to the reader to find out why.

From,
Nice coder

int MSB(unsigned x){	int n = 0;	for(; x >>= 1; ++n);	return n;}