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

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

Answer 2

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 3

How about implementing a kind of binary search?

Look at the low bits resulting from a bit wise and of a mask value that is all ones in the low half. If that value is zero you know the smallest bit is in the upper half of the number.

other wise cut the thing in half and go again.

Answer 4

How about something like this? It reduces the number of loops considerably.

int shifts = 0;
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits
{
    shifts = 48;
}
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits
{
    shifts = 40;
}
else
// etc

bits >>= shifts;  // do all the shifts at once

// this will loop at most 8 times
for(i = 0;!(bits & 1ULL);i++)
    bits >>= 1;

index = shifts + i;

Answer 5

You can isolate the lowest set bit with x & (~x + 1); this gives you the lowest bit value, not the index (e.g., if x = 01101000, then the result is 00001000). The fastest way I know of to get from there to an index is probably a switch statement:

switch(x & (~x + 1))
{
  case     0ULL: index = -1; break;
  case     1ULL: index =  0; break;
  case     2ULL: index =  1; break;
  case     4ULL: index =  2; break;
  ...
  case 9223372036854775808ULL: index = 63; break;
}

Ugly, but no looping involved.

Answer 6

I wrote two functions, they are returning the same result as ffsll().

int func1( uint64_t n ){
  if( n == 0 ) return 0;
  n ^= n-1;
  int i = 0;
  if( n >= 1ull<<32 ){ n>>=32; i+=32; }
  if( n >= 1ull<<16 ){ n>>=16; i+=16; }
  if( n >= 1ull<< 8 ){ n>>= 8; i+= 8; }
  if( n >= 1ull<< 4 ){ n>>= 4; i+= 4; }
  if( n >= 1ull<< 2 ){ n>>= 2; i+= 2; }
  if( n >= 1ull<< 1 ){         i+= 1; }
  return i+1;
}

int func2( uint64_t n ){
  return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0;
}

I don't know which is the fastest: ffsll(), func1() or func2() ?

Answer 7

you can halve the complexity of your algorithm checking first if your number is odd or even. If it is even you have the lowest order bit is the first one.

For odd cases you can implement such a binary search...

Answer 8

This might work for 32 bits. Should be easy enough to extend to 64.

// all bits left of lsb become 1, lsb & right become 0
y = x ^ (-x);

// XOR a shifted copy recovers a single 1 in the lsb's location
u = y ^ (y >> 1);

// .. and isolate the bit in log2 of number of bits
i0 = (u & 0xAAAAAAAA) ?  1 : 0;
i1 = (u & 0xCCCCCCCC) ?  2 : 0;
i2 = (u & 0xF0F0F0F0) ?  4 : 0;
i3 = (u & 0xFF00FF00) ?  8 : 0;
i4 = (u & 0xFFFF0000) ? 16 : 0;
index = i4 | i3 | i2 | i1 | i0;

Obviously, if there is some way to have the hardware do it, i.e., if special CPU instructions are available, that is the way to go.

Answer 9

If using Visual Studio, _BitScanForward:

• http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx (_BitScanForward)

For gcc, try __builtin_ctz or __builtin_ffs:

• http://developer.apple.com/mac/library/documentation/DeveloperTools/gcc-4.0.1/gcc/Other-Builtins.html (random gcc intrinsics documentation)

As always the generated code should be consulted to ensure the correct instructions are being generated.