I stumbled to this thread while searching the forum and because there's no (extremely good) solutions, I decided to give it a go. Using the tricks in the book "Hacker's Delight".
So, the goal is to find out the index of the Nth rightmost (least significant) bit that is set.
From the book:
Use the following formula to isolate the rightmost 1-bit, producing 0 if none (e.g., 01011000 -> 00001000):
x & (-x)
Complete function:
So, the goal is to find out the index of the Nth rightmost (least significant) bit that is set.
From the book:
Use the following formula to isolate the rightmost 1-bit, producing 0 if none (e.g., 01011000 -> 00001000):
x & (-x)
Complete function:
C:
int find_nth_bit(unsigned int x, int n) {
while(--n) {
x = x ^ (x & (-x)); // Turn off the rightmost bit
}
x = x & (-x); // we have now isolated the Nth rightmost bit
// Find the isolated bit position.
// This can be optimized many ways. Using a look-up-table or switch-case for example.
while(x) {
n++;
x = x >> 1;
}
return n;
}
Last edited: