424,984 Members | 1,456 Online
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
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