Index of lowest order bit

Question

I want to find the fastest way to get the index of the lowest order bit of a long long. ie:

00101001001000 -> 3

Solutions involving looping and shifting are too slow. ie:

int i;
if(bits == 0ULL) {
  i = 64;
} else {
  for(i = 0;!(bits & 1ULL);i++)
    bits >>= 1;
}

EDIT: Info on usage

The function that uses ffsll can't really reduce its usage, but here it is (simplified of course). It just iterates through the indices and does something with them. This function is perhaps the most widely used function in my whole application despite a lot of caching of its value. It's a legal move generator in my alpha-beta search engine.

while(bits){
  index = ffsll(bits);
  doSomething(index);
  index &= index-1;
}

Answer 1

Intel has specialized instructions for finding either lowest or highest order set bit. BSF seems like what you need. as far as doing it in plain C, maybe the bit twiddling hacks page has what you need.

At the very least you could use a table of nibbles or bytes to speed things up. Something like this (demonstrated for int, but easily changeable to longlong as needed).

/*
0000 - 0
0001 - 1
0010 - 2
0011 - 1
0100 - 3
0101 - 1
0110 - 2
0111 - 1
1000 - 4
1001 - 1
1010 - 2
1011 - 1
1100 - 3
1101 - 1
1110 - 2
1111 - 1
*/

int ffs(int i) {
    int ret = 0;
    int j = 0;
    static const int _ffs_tab[] = 
        { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 };

    while((i != 0) && (ret == 0)) {
        ret = _ffs_tab[i & 0x0f];

        if(ret > 0) {
            break;
        }

        i >>= 4;
        j += 4;

        /* technically the sign bit could stay, so we mask it out to be sure */
        i &= INT_MAX;
    }

    if(ret != 0) {
        ret += j;
    }

    return ret;
}

Answer 2

The fastest I've found is ffsll(long long) in string.h.