By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,984 Members | 1,456 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,984 IT Pros & Developers. It's quick & easy.

least significant set bit

P: 10
Hello,

I'm trying to find the least significant set bit (i.e. the first '1' bit in an int) through just bit twiddling, but I can't get it without resorting to a loop. My original idea was to reverse the bits in an int and find the most significant bit then subtract it from 31 to get the position of the LSB. Is there a way to get the LSB of an int using just bit manipulations?

e.g., 0b0101 would return 0001,
0b0000 would return 0000,
0b1110 would return 0010.


Thanks
Aug 13 '07 #1
Share this Question
Share on Google+
4 Replies


Expert 10K+
P: 11,448
(x^x-1)+1>>1

no comments though: figure it out.

kind regards,

Jos
Aug 13 '07 #2

P: 10
(x^x-1)+1>>1

no comments though: figure it out.

kind regards,

Jos
Hmm, thanks for the help, but it seems that this solution breaks when it encounters 0x80000000 - instead of returning itself, it returns 0! Most likely since it relies on the fact that (x ^(x-1) + 1 will place the LSB one 'place' up and then shifts it back down; MIN_INT ^ (MIN_INT - 1) results in -1 and adding one makes that 0...

Edit: Ok, i figured out a better way once i worked through why your algotithm works and breaks for MIN_INT ... Thanks for your help!
Aug 13 '07 #3

Expert 10K+
P: 11,448
Edit: Ok, i figured out a better way once i worked through why your algotithm works and breaks for MIN_INT ... Thanks for your help!
You're welcome of course; what did you do to make it work for 0x80000000 as well?

kind regards,

Jos
Aug 13 '07 #4

P: 10
You're welcome of course; what did you do to make it work for 0x80000000 as well?

kind regards,

Jos
(x & -x) which is equivalent to (x & (~x + 1))
Aug 13 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.