Hi all,
just want to ask whether someone knows a very fast algoirthm to get the LSB position of a 16/32bit variable?
Example:
0x0013 -> LSB position: 0 (bit 0)
0x00A8 -> LSB position 3 (bit 3)
0x00C0 -> LSB position 6 (bit 6)
Tried to google but couldn't find anything.
Btw, i don't want to use big lookup table for this.
Thanks
Regards,
Leo Hendrawan
You can simply shift right the variable until the first bit is equal to 1:
int tmp = var; // Temporary copy of the variableint cnt = 0; // Bit counterif (tmp != 0) // To avoid infinite loops while (!(tmp & 0x01)) { tmp >>= 1; cnt++; }// 'cnt' contains the LSB position
Hi Emanuelle,
thanks for the reply. I know this simple method. What i need is something which works really fast.
lhendWhat i need is something which works really fast
What, exactly, do you mean by, "really fast"?
The loop would only have to spin a max of 16/32 times - so it's not exactly "slow"!
Other than a lookup table, a string of ifs could well be fastest - especially if you have some prior knowledge of the "most likely" outcome(s)...
Hi Andy,
thanks for the reply. Actually i am developing a light-weight scheduler system for MSP430 value line devices. Should be ready soon, but i want to do some optimizations. One of them is basically covered in this question. I have a 16 bit variable in my scheduler system which represents the tasks which are ready to be executed.
What i want is something like these:
http://graphics.stanford.edu/~seander/bithacks.html
for example i found that:: x &= x - 1 will give you the LSB only bit set of the variable x. But what i want is something different, i want to get the position of the LSB.
Binary search and lookup:
static const signed char g_lsb[16] ={ 4, /* 0b0000 *//*Error condition?*/ 0, /* 0b0001 */ 1, /* 0b0010 */ 0, /* 0b0011 */ 2, /* 0b0100 */ 0, /* 0b0101 */ 1, /* 0b0110 */ 0, /* 0b0111 */ 3, /* 0b1000 */ 0, /* 0b1001 */ 1, /* 0b1010 */ 0, /* 0b1011 */ 2, /* 0b1100 */ 0, /* 0b1101 */ 1, /* 0b1110 */ 0, /* 0b1111 */};int lsb_pos(unsigned int x){ int base; if(x & 0x00FF) base = (x & 0x000F) ? 0 : 4; else base = (x & 0x0F00) ? 8 : 12; x >>= base; x &= 0xF; return(g_lsb[x] + base);}
The above should be a fixed cost algorithm. Regardless of the value of n.
Hi Norman,
yes, i thought also about binary search with something like this. I'll let the discussion to be opened waiting for some other inputs.
thanks again.
lhend... for example i found that:: x &= x - 1 will give you the LSB only bit set of the variable x. But what i want is something different, i want to get the position of the LSB.
I do not get it. But I think y = (x ^ (x - 1)) + 1 will give you 2**(the position of the LSB)
For example: x = 0x30C0; the LSB is BIT 7
y = (0x30C0 ^ (0x30BF)) + 1 = 0x007F + 1 = 0x0080; which is 2**7
Hi OCY,
old_cow_yellow lhend... for example i found that:: x &= x - 1 will give you the LSB only bit set of the variable x. But what i want is something different, i want to get the position of the LSB. I do not get it.
I do not get it.
For example let's say for the sake of simplicity, we take number 0xF4 = 1111 0100 bin. to get the LSB (not the position), we take -(0xF4) = 0xC0 -> using 2 complements.
If we then do 0xF4 & 0xC0, this will result to 0x04, which is basically the LSB. But what i want is the bit position which in this case 2 (bit 2).
Hi Leo,
The first "trick" you mentioned actually clears the least-significant set bit. Here is the longhand version of the trick:
x = x & (x-1);
For example, take the number 0xF4 = 1111 0100. Bitwise AND with 0xF3 = 1111 0011. Gives 0xF0. We cleared the least-significant set bit.
Then you alluded to a second "trick" without really showing it first:
x = x & -x;
This trick clears everything except the least-significant set bit (just like OCYs method).
For example, take the number 0xF4 = 1111 0100. -0xF4 is 0x0C = 0000 1100. Anded together you get 0x04.
However, as you say, you really want to convert that 0x04 into its bit position. That is a log2 function. Many microprocessors and DSPs have a native log2 instruction. That's because there is no quick arithmetic transform between these two domains.
Jeff
Ups..
you're right Jeff... it is x &= -x which will give the LSB set only in the variable, sorry for the confusion :)
the fastest thing to get the position of the LSB is a lookup table. Takes 65536 bytes for a 16 bit value.However, next optimizaiton step is only a 256 byte lookup table and a bit more code.
const unsigned char lookup[256] = {0,1,2,1,3,1,2,1,4,...};
int x = lookup[y&0xff];if(!x) x= 8+ lookup[y>>8];x--;
then contains the bit number of the LSB or -1 if there was no bit set.
For a 32 bit value, two more lines have to be added, similar to the second one.
I don't think you can get it faster.
_____________________________________Before posting bug reports or ask for help, do at least quick scan over this article. It applies to any kind of problem reporting. On any forum. And/or look here.If you cannot discuss your problem in the public, feel free to start a private conversation: click on my name and then 'start conversation'. But please do so only if you really cannot do it in a public thread, as I usually read all threads. And I prefer to answer where others can profit from it (or contribute to it) too.
Hi JMG,
thanks for the input also. Yes lookup table would be the fastest way, but i can't afford that (even for the 256 bytes table). My complete scheduler (with all features enabled, but no application code) now only consumes less than 1 KB. Giving away hundreds of bytes for the lookup table would be too much.
It seems there is no real silver bullet in this case, but thanks again for the input, guys.
lhend i can't afford that (even for the 256 bytes table)
Of course, doing the lookup table approach in assembly will allow for some more efficiency and save some more cycles and bytes.
Jens-Michael Gross Of course, doing the lookup table approach in assembly will allow for some more efficiency and save some more cycles and bytes.
This is a very good point which i also notice, that's why i am going to put this routine in the "portable" file which can be adapted to the hardware capability.
Will let you know if i am ready to release the code (actually the code itself is finished, but i still need to make better documentation :) )
Another compromise between speed and size would be:
int FindLsb( int val) { if( val & 0x01) return 1; if( val & 0x02) return 2; if( val & 0x04) return 3; . . if( val & 0x80) return 16;
return 0; }